[C++] 백준/BOJ - 13172 : ∑

문제 이해 단계

https://www.acmicpc.net/problem/13172

13172번: Σ

문제가 거의 비문학 지문이다.
여기서 문제 풀이에 필요한 정보만 뽑아보자.

1.
각 주사위에서 얻을 수 있는 기댓값은 a * b^(-1) modX를 계산해야 한다.
여기서 a는 모든 면에 적힌 숫자의 합이고, b는 주사위 면에 개수이다.

2.
b^(-1)는 b의 모듈러 곱셈에 대한 역원인데,
구하는 방법은 b^(X-2) = b^(-1) modX이다.

3.
모든 주사위를 한 번씩 던졌을 때 나온 숫자들의 합의 기댓값을 얻기 위해서는
각 주사위에서 얻을 수 있는 기댓값을 다 더하면 된다.

4. 모듈러 연산의 수는 항상 1,000,000,007로 고정되어 있다.

사실 위에 정보만 알고 문제를 풀면 된다.

 

---

문제 접근 단계

제한사항부터 살펴보면 주사위 면의 수 N와 모든 면의 합 S가 최대 10^9까지이다.

여기서는 곱하는 연산이 있기 때문에 Int형 자료형이 넘어갈 것이다.
따라서 Long Long 자료형으로 받아주도록 한다.

 

---

문제의 핵심

사실 이 문제의 핵심은 a * b^(-1) modX 이 계산을 하는 것이다.

여기서 X는 1,000,000,007로 고정이고 a도 입력으로 알아서 주어진다.
그렇기 때문에 우리가 구해야 할 것은 b^(-1)이다.

b에 관한 정보는 입력으로 주어지지만
b의 역원은 우리가 구해야 한다.

다행히도 이 값을 구하는 힌트는 문제에서 줬다.

b^(X-2) = b^(-1) modX 여기서 구하면 된다.

X는 무조건 1,000,000,007부터 시작이니까
b^1,000,000,005 = b^(-1) mod(1,000,000,007)를 구하라는 건데

이걸 일일이 구한다면 당연히 10억 번을 곱해야 하기 때문에
1초가 넘어가 시간초과가 뜬다.

그래서 예전에 풀었던 곱셈과 같은 원리로 분할정복으로 이 문제를 해결한다.

자세한 원리는 곱셈 문제와 같기 때문에 아래에 링크를 걸어두겠다

. https://howudong.tistory.com/297

[C++] 백준 1629 - 곱셈

이제 이를 각 주사위마다 구해주고 더해주기만 하면 된다.
물론 이 값을 1,000,000,007로 나눠주는 것을 잊지 않도록 한다.

 

---

문제 구현 단계

#include <iostream>
#include <cmath>

using namespace std;

#define MOD 1000000007 // 나눠주는 X
int N,S;

// 분할정복(b의 역원 구하기) x -> b, y -> 지수
long long getReverse(long long x,long long y){
    if(y == 1) return x;
    
    if(y % 2 == 1) return (x * getReverse(x,y-1))%MOD;

    long long val = getReverse(x,y/2);
    return (val*val)%MOD;
}
int main(){
    cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

    int M;
    cin >> M;
    long long ans = 0;
    while(M--){
        cin >> N >> S;
        long long val = (S*getReverse(N,MOD-2))%MOD;
        ans += (val%MOD);
    }
    cout << ans%MOD;
}

코드는 엄청나게 간단하다.
코드만으로 충분히 이해하리라고 생각한다.

풀이는 여기까지이다.

 

---

시행착오

문제를 이해하는데만 30분 이상 걸린 것 같다.

이 문제가 분할정복 문제라는 것을 깨닫지 못한 것이 한심하다.
풀이를 보자마자 왜 이 당연한 생각을 못했지라는 자책감이 들었다.

예전에 풀어봤던 문제와 유사한 문제를 틀려서 그런지 더 짜증 난다.

https://toss.me/howudong

howudong님에게 보내주세요