[Baekjoon] 13172. 시그마
문제 설명
문제
실제로 존재하는지 아닌지는 차치하고, 당신에게 삼면체 주사위가 있어서 이 주사위를 굴린다고 생각해보자. 주사위를 굴렸을 때 각 면이 나올 확률은 모두 동일하게 1/3 이다. 한 면에는 1, 다른 한 면에는 2, 남은 한 면에는 4가 적혀있다고 하면 주사위를 굴렸을 때 나오게 되는 숫자의 기댓값은 과연 몇일까? 간단하게도 셋의 평균인 7/3이 될 것이다.
이 문제를 조금 확장해서, “N면체 주사위의 각 면에 적힌 수가 주어졌을 때, 주사위를 굴렸을 때 각 면이 나올 확률이 모두 같다면 주사위를 굴렸을 때 나오게 되는 수의 기댓값은 과연 몇일까?”라는 문제가 주어졌다고 하자. 위의 예시에 대한 답을 소수로 출력한다면 2.33333333…일텐데, 무한한 자릿수를 모두 출력할 수는 없으니 적당히 끊어서 출력할 것이고, 이 끊긴 소수를 채점 프로그램이 다시 입력받아서 정답과 비교한다고 하면 결과가 얼마나 부정확할 것인가? 그렇기에 답을 정확히 판별하기 위해 출력하고자 하는 분수를 기약분수로 만들어 분모와 분자를 직접 출력하도록 했던 시기가 있었다.
이제 문제를 조금 더 확장하여, M개의 주사위가 있어서 이 중 i번째 주사위가 Ni면체 주사위이고 모든 면에 적힌 수를 더한 값이 Si일 때, 각 주사위에 대해서 주사위를 던졌을 때 주사위의 각 면이 나올 확률이 동일하다고 가정한 상태에서 모든 주사위를 각각 한 번씩 던졌을 때 나온 수들의 합의 기댓값을 구하는 문제를 만들었다. 확률변수 X의 기댓값을 E(X)로 나타내면, 기댓값의 선형성에 의해서 두 확률변수 X, Y에 대해 E(X + Y) = E(X) + E(Y)가 성립하므로, 이 문제의 답을 아래와 같이 간단하게 나타낼 수 있다.
S1/N1 + S2/N2 + … + SM/NM
즉, 각 주사위에서 나오게 되는 수의 기댓값을 모두 더하면 답이 되는 것이다. 이 답을 정확하게 출력하기 위해, 모든 분수(여기서는 각 주사위의 기댓값)를 통분한다고 생각해보자. 이 분수의 분모와 분자의 값이 어떤 범위까지 치솟게 될 것인가? 즉, 분모와 분자를 모두 저장하고 있게 되면, 두 분수의 합을 구할 때 분모와 분자를 적정한 범위 내에서 계산해낼 수 없다는 문제에 부딪히게 된다. “그렇다면 분모와 분자를 어떤 모듈러 상에서 가지고 있으면 되지 않을까?”라고 생각할 수 있지만, 그러면 분모와 분자를 약분할 수가 없게 된다. 그렇기에, 분수를 다음과 같이 모듈러 상에서 하나의 정수로 가지고 있는 방법을 채택하게 되었다.
어떤 분수가 기약분수로 나타냈을 때 a/b이면, 이 분수는 a × b-1 mod X (X는 소수)으로 대신 계산하도록 한다. 여기서 b-1은 b의 모듈러 곱셈에 대한 역원이다.
b의 모듈러 곱셈에 대한 역원 b-1은 대체 어떤 수인 것일까? 이 수는 다음과 같은 성질을 만족하는 정수이다.
b-1 × b ≡ 1(mod X)
소수 모듈러에서만 성립하는 페르마의 소정리에 의해 bX - 1 ≡ 1 (mod X)가 성립하기에, bX - 2 ≡ b-1 (mod X) 역시 성립함을 알 수 있다.
이해를 돕기 위해 X를 11로 두고 Q = 7/3 을 계산해보자. 3-1 ≡ 4 (mod 11)이므로, Q ≡ 7 × 4 ≡ 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번째 주사위가 Ni면체 주사위이며, 모든 면에 적힌 숫자를 더한 값이 Si일 때, 각 주사위에 대해서 주사위를 던졌을 때 주사위의 각 면이 나올 확률이 동일하다면, 모든 주사위를 한 번씩 던졌을 때 나온 숫자들의 합의 기댓값을 구하는 문제를 해결해보자.
입력
첫 번째 줄에는 주사위의 수를 나타내는 정수 M(1 ≤ M ≤ 104)이 주어진다.
다음 M개의 줄은 각 주사위의 정보를 나타내며, 이 중 i(1 ≤ i ≤ M)번째 줄에는 Ni, Si(1 ≤ Ni, Si ≤ 109)가 공백으로 구분되어 주어진다.
출력
모든 주사위를 한 번씩 던졌을 때 나온 숫자들의 합의 기댓값을 출력한다. 정확한 판별을 위해, 답을 기약분수로 나타내었을 때 a/b가 된다면, (a × b-1) mod 1,000,000,007을 대신 출력하도록 한다. b-1은 b의 모듈러 곱셈에 대한 역원이다. 이 문제에서는 가능한 모든 입력에 대해 답이 존재한다.
예제 입력 1
1
3 7
예제 출력 1
333333338
힌트
모듈러가 11에서 1,000,000,007이 되어 답이 달라졌지만, 역시 3을 곱한 다음 1,000,000,007으로 나눈 나머지는 7이 된다.
출처
Contest > kriiicon > 제4회 kriiicon P2번
- 문제를 만든 사람: august14
알고리즘 분류
문제 풀이
# Math # Divide&Conquer
분할정복을 이용한 수학 문제입니다.
풀이 과정
문제가… 엄청 장황하다. 개념도 쉽지는 않아 보인다.
하지만 이런 문제일수록, 실제로 요구하는 부분은 어렵지 않은 경우가 많다! 차근차근 읽어보면, 아래 두 가지 식이 핵심임을 알 수 있다.
a/b => a × b^(-1) mod X (X는 소수)b^(X-2) ≡ b^(-1) (mod X)
이로부터 기약분수 a/b를 0~X-1 사이의 정수로 변환하는 식을 구할 수 있다.
a/b => a × b^(X-2) (mod X)
그리고 이 때 X는 10^9 + 7이다.
여기까지 왔다면 b^(X-2)만 구하면 되는데, 이 때 X가 매우 크기 때문에 이를 분할 정복으로 구하는 것이다. 제곱수를 분할정복으로 구하는 방법은 자주 사용되니 알아두자.
전체 코드
전체 코드입니다.
import sys
from math import gcd
X = int(1e+9) + 7
def get_converted_integer(a, b): # 기약분수(a/b)를 정수로 변환
return a * get_square_number(b, X-2) % X
def get_square_number(n, exp): # 제곱수 계산
if exp == 1:
return n
if exp % 2 == 0:
root_n = get_square_number(n, exp//2)
return root_n * root_n % X
else:
return n * get_square_number(n, exp-1) % X
M = int(sys.stdin.readline())
ans = 0
for _ in range(M):
# n 면체, 총합 s
n, s = map(int, sys.stdin.readline().rstrip().split())
# 기약분수 구하고
_gcd = gcd(n, s)
a, b = s // _gcd, n // _gcd
# 정수로 바꾸고
num = get_converted_integer(a, b)
# 답에 더하고
ans = (ans + num) % X
print(ans)
배운 점
- 긴 문제일수록 차분히 문제를 읽고, 핵심을 파악하자! 문제가 길수록 요구하는 부분은 크지 않은 경우가 많다.
- 제곱 수를 분할정복으로 구하는 알고리즘은 알아두자!
Leave a comment