백준 13172번
오늘 풀어본 문제는 백준의 13172번 문제1이다. 문제 풀이에 사용한 언어는 C++ 이다.
solved.ac 기준 CLASS
문제 정보
이 문제의 내용과 조건은 다음과 같다.
문제
실제로 존재하는지 아닌지는 차치하고, 당신에게 삼면체 주사위가 있어서 이 주사위를 굴린다고 생각해보자. 주사위를 굴렸을 때 각 면이 나올 확률은 모두 동일하게 $1/3$ 이다. 한 면에는 $1$, 다른 한 면에는 $2$, 남은 한 면에는 $4$ 가 적혀있다고 하면 주사위를 굴렸을 때 나오게 되는 숫자의 기댓값은 과연 몇일까? 간단하게도 셋의 평균인 $7/3$ 이 될 것이다.
이 문제를 조금 확장해서, “$N$ 면체 주사위의 각 면에 적힌 수가 주어졌을 때, 주사위를 굴렸을 때 각 면이 나올 확률이 모두 같다면 주사위를 굴렸을 때 나오게 되는 수의 기댓값은 과연 몇일까?”라는 문제가 주어졌다고 하자. 위의 예시에 대한 답을 소수로 출력한다면 $2.33333333\cdots$ 일텐데, 무한한 자릿수를 모두 출력할 수는 없으니 적당히 끊어서 출력할 것이고, 이 끊긴 소수를 채점 프로그램이 다시 입력받아서 정답과 비교한다고 하면 결과가 얼마나 부정확할 것인가? 그렇기에 답을 정확히 판별하기 위해 출력하고자 하는 분수를 기약분수로 만들어 분모와 분자를 직접 출력하도록 했던 시기가 있었다.
이제 문제를 조금 더 확장하여, $M$ 개의 주사위가 있어서 이 중 $i$ 번째 주사위가 $N_i$ 면체 주사위이고 모든 면에 적힌 수를 더한 값이 $S_i$ 일 때, 각 주사위에 대해서 주사위를 던졌을 때 주사위의 각 면이 나올 확률이 동일하다고 가정한 상태에서 모든 주사위를 각각 한 번씩 던졌을 때 나온 수들의 합의 기댓값을 구하는 문제를 만들었다. 확률변수 $X$ 의 기댓값을 $E(X)$ 로 나타내면, 기댓값의 선형성에 의해서 두 확률변수 $X$, $Y$ 에 대해 $E(X + Y) = E(X) + E(Y)$ 가 성립하므로, 이 문제의 답을 아래와 같이 간단하게 나타낼 수 있다.
\[S_1/N_1 + S_2/N_2 + ... + S_M/N_M\]즉, 각 주사위에서 나오게 되는 수의 기댓값을 모두 더하면 답이 되는 것이다. 이 답을 정확하게 출력하기 위해, 모든 분수(여기서는 각 주사위의 기댓값)를 통분한다고 생각해보자. 이 분수의 분모와 분자의 값이 어떤 범위까지 치솟게 될 것인가? 즉, 분모와 분자를 모두 저장하고 있게 되면, 두 분수의 합을 구할 때 분모와 분자를 적정한 범위 내에서 계산해낼 수 없다는 문제에 부딪히게 된다. “그렇다면 분모와 분자를 어떤 모듈러 상에서 가지고 있으면 되지 않을까?”라고 생각할 수 있지만, 그러면 분모와 분자를 약분할 수가 없게 된다. 그렇기에, 분수를 다음과 같이 모듈러 상에서 하나의 정수로 가지고 있는 방법을 채택하게 되었다.
어떤 분수가 기약분수로 나타냈을 때 $a/b$ 이면, 이 분수는 $a \times b^{-1} \mod X$ ($X$ 는 소수)으로 대신 계산하도록 한다. 여기서 $b^{-1}$ 은 $b$ 의 모듈러 곱셈에 대한 역원이다.
$b$ 의 모듈러 곱셈에 대한 역원 $b^{-1}$ 은 대체 어떤 수인 것일까? 이 수는 다음과 같은 성질을 만족하는 정수이다.
\[b^{-1} \times b \equiv 1 \mod X\]소수 모듈러에서만 성립하는 페르마의 소정리에 의해 $bX - 1 \equiv 1$ (mod X)가 성립하기에, bX - 2 \equiv b-1 (mod X) 역시 성립함을 알 수 있다.
이해를 돕기 위해 $X$ 를 $11$로 두고 $Q = 7/3$ 을 계산해보자. $3^{-1} \equiv 4 \mod 11$ 이므로, $Q \equiv 7 \times 4 \equiv 6 \mod 11$ 이다. 이 $Q$ 에 $3$ 을 곱한 다음 $11$ 로 나눈 나머지를 구해 보면 $7$ 이 나오므로, $6$ 이라는 정수가 $7/3$ 을 적절히 저장하고 있다는 것을 알 수 있다.
분수(유리수)를 이와 같은 방식으로 나타낸다면, 두 분수의 덧셈, 뺄셈, 곱셈은 $\mod X$ 에서 두 정수를 가지고 계산하듯이 처리하고, 나눗셈은 나누는 분수의 곱셈에 대한 역원을 구한 후 그 역원을 $\mod X$ 에서 곱하는 것으로 처리한다면, 분수를 정확히 출력하기 위해 통분을 하거나 기약분수로 만드는 골치아픈 일을 할 필요가 없어진다!
그러나 이 방법에도 문제가 있는 것은 마찬가지이다. 앞의 예에서 $7/3$ 을 $6$ 으로 저장했지만, 그냥 $6/1$ 도 $6$ 으로 저장할 것이다. 즉 서로 다른 두 분수도 모듈러 상에서 같은 정수로 저장하여, 정확한 판별을 한다는 우리의 목적에 부합하지 않는 것이다. 또다른 문제로는, 분모가 소인수로 $X$ 를 가질 때에는 역원을 계산할 수 없어서 모듈러로 나타낼 수가 없다는 점이 있다. 이러한 문제를 해결하기 위해 모듈러를 $1,000,000,007$ 와 같은 큰 소수로 하는데, 이를 통해 서로 다른 두 분수가 같은 정수로 나타나게 되는 확률을 낮추고, 분모가 가질 수 있는 소인수의 범위를 늘리는 효과를 볼 수 있다. 그는 이런 방식이 그래도 가장 정확한 방식이라고 생각하게 되었다.
이제 이 방식으로 $M$ 개의 주사위가 있고, $i$ 번째 주사위가 $N_i$ 면체 주사위이며, 모든 면에 적힌 숫자를 더한 값이 $S_i$ 일 때, 각 주사위에 대해서 주사위를 던졌을 때 주사위의 각 면이 나올 확률이 동일하다면, 모든 주사위를 한 번씩 던졌을 때 나온 숫자들의 합의 기댓값을 구하는 문제를 해결해보자.
입력
첫 번째 줄에는 주사위의 수를 나타내는 정수 $M$ $(1 \leq M \leq 104)$ 이 주어진다.
다음 M개의 줄은 각 주사위의 정보를 나타내며, 이 중 $i$ $(1 \leq i \leq M)$ 번째 줄에는 $N_i$, $S_i$ $(1 \leq N_i, S_i \leq 109)$ 가 공백으로 구분되어 주어진다.
출력
모든 주사위를 한 번씩 던졌을 때 나온 숫자들의 합의 기댓값을 출력한다. 정확한 판별을 위해, 답을 기약분수로 나타내었을 때 $a/b$ 가 된다면, $(a \times b-1) \mod 1,000,000,007$ 을 대신 출력하도록 한다. $b^{-1}$ 은 $b$ 의 모듈러 곱셈에 대한 역원이다. 이 문제에서는 가능한 모든 입력에 대해 답이 존재한다.
풀이과정
1번째 시도
처음 문제를 보고 길이가 굉장히 길어서 당황했지만, 천천히 읽어보니 문제에서 요구하는 사항은 다음과 같았다.
- 주사위 들의 정보를 입력받는다.
- 각 주사위의 기댓값을 특정한 형태로 표현한다.
- 그것들을 모두 더한 뒤 출력한다.
이 때 ‘특정한 형태’라고 하면, 나눗셈의 과정에서 실수연산을 적용하는 대신 모듈러 연산에서의 역원을 곱하는 방식으로 나타내는 것을 의미한다.
문제에서는 한 가지 정보를 더 제공해주는데, 모듈러 역원을 계산하는 과정에서 문제 상황이 특정 조건을 만족하기 때문에 거듭제곱을 계산하는 것으로 역원을 쉽게 구할 수 있다고 한다. 이 문제에서는 이걸 활용해야 한다는 것을 알 수 있었다.
코드는 다음과 같이 작성하였다.
#include <bits/stdc++.h>
using namespace std;
long long int modularInverse(long long int A, long long int mod);
long long int power(long long int base, long long int exponent, long long int mod);
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
constexpr long long int mod = 1000000007;
long long int M;
cin >> M;
long long int total = 0;
for (long long int i = 0; i < M; i++) {
long long int N, S;
cin >> N >> S;
total += (S * modularInverse(N, mod)) % mod;
}
cout << total;
return 0;
}
long long int modularInverse(long long int A, long long int mod) {
return power(A, mod - 2, mod);
}
long long int power(long long int base, long long int exponent, long long int mod) {
if (exponent == 0) {
return 1;
}
else if (exponent == 1) {
return base % mod;
}
else {
long long int halfPowered = power(base, exponent / 2, mod);
if (exponent % 2 == 0) {
return (halfPowered * halfPowered) % mod;
}
else {
return (halfPowered * halfPowered * base) % mod;
}
}
}
실행 결과 ‘틀렸습니다’ 가 떴다.
7번째 시도
이 문제를 해결하기 위해 꽤 많은 시도가 있었다. 나눗셈 과정에서 두 수의 최대공약수를 구하여 나누고 계산하는 시도도 해보았고, 나머지 연산을 떡칠하는 시도또한 해보았다.
모조리 실패하였고, 결국 나는 다른 방식을 시도해보기로 했다. 모듈러 역원을 구하는 과정에서 분할정복을 이용한 거듭제곱 함수를 이용하였는데, 구현히 잘못되었나 싶어 지우고 다시 구현해보았다.
원래는 재귀함수 방식으로 구현하였는데, 이번에는 재귀함수를 이용하지 않고 함수를 작성해보았다.
코드는 다음과 같이 수정하였다.
#include <bits/stdc++.h>
using namespace std;
long long int power(long long int base, long long int exponent, long long int mod);
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
constexpr long long int mod = 1000000007;
long long int M;
cin >> M;
long long int total = 0;
while (M--) {
long long int N, S;
cin >> N >> S;
total += (S * power(N, mod - 2, mod)) % mod;
}
cout << total % mod;
return 0;
}
long long int power(long long int base, long long int exponent, long long int mod) {
long long int result = 1;
while (exponent) {
if (exponent % 2 == 1) {
result = result * base % mod;
}
exponent = exponent / 2;
base = base * base % mod;
}
return result;
}
그러자 모든 테스트 케이스를 통과하고 정답이 나오는 것을 확인할 수 있었다.
마무리
간만에 맞왜틀을 연신 외치게 되는 문제였다. 분명히 아무런 문제가 없었던 것 같은데 계속 틀려서 마음이 무척이나 답답했다.
문제의 원인이 전혀 생각도 못했던 거듭제곱 함수였다는 것이 충격적이었다. 앞으로는 맞왜틀이 발생할 때면 모든 함수를 의심해봐야 할 것 같다.
오늘의 PS는 여기까지!
1: https://www.acmicpc.net/problem/13172