[백준 알고리즘 / 13172번/ 파이썬] Σ

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

13172번: Σ

문제: 모든 주사위를 한 번씩 던졌을 때 나온 숫자들의 합의 기댓값을 구하는 문제입니다.

 

풀이 방법: 분할정복

 

풀이 코드: 

import sys
import math

n = int(input())
modular = 1000000007
total = 0
numerator = []
dominator = []


def getLcd(dominator:list):
    dom = dominator[0]
    for i in range(len(dominator)-1):
        dom = math.lcm(dom,dominator[i+1])
    return dom

def getFraction(numerator:list,dominator:list,dom):

    sumNumerator = 0

    for i in range(len(dominator)):
        sumNumerator += numerator[i] * (dom//dominator[i])
    return (sumNumerator,dom)


def DQ(num,x):
    if x == 1:
        return num
    tmp = DQ(num,x//2)
    if x % 2 == 1:
        return tmp *tmp* num % modular
    else:
        return tmp * tmp % modular


for _ in range(n):
    n, s = map(int,sys.stdin.readline().rstrip().split())
    numerator.append(s)
    dominator.append(n)

sumN, lcd = getFraction(numerator,dominator,getLcd(dominator))

total = DQ(lcd,modular-2)

print((sumN*total) % modular)

 

풀이 설명:

 

먼저 기대값을 계산하는 법에 대해서 설명을 드리겠습니다.

 

문제 예시인 n = 3, s = 7 일 경우,  7 * ( 3 ^ -1 ) mod 1000000007의 경우는 7 * ( 3 ^ 1000000005 ) mod 1000000007과 같습니다.

 

그리고 예를들어 기약 분수가 7/3 , 6/5 두개가 주어졌다면, 53/15에 대하여 연산해주면 됩니다.

표현하자면, 53 * ( 15 ^ 1000000005) mod 1000000007로요.

 

보시면 아시겠지만, 1000000005 제곱을 해주어야 하기 때문에 분할 정복을 활용하여 문제를 풀어주었습니다.

 

코드는 다음과 같이 구성하였습니다.

 

for _ in range(n):
    n, s = map(int,sys.stdin.readline().rstrip().split())
    numerator.append(s)
    dominator.append(n)

분자, 분모의 값은 입력 받아 리스트에 저장해주었습니다.

 

def getLcd(dominator:list):
    dom = dominator[0]
    for i in range(len(dominator)-1):
        dom = math.lcm(dom,dominator[i+1])
    return dom

위 코드는 분모가 될 최소 공배수를 구하는 코드입니다.

math.lcm 함수를 통해 분모들을 비교하면서 최종적인 최소공배수를 구해주었습니다.

예를 들어 3,5,7이 있다면 (3 , 5 , 7)의 최소 공배수는 3과 5의 최소 공배수인 15와 7의 최소 공배수와 동일하기 때문에 다음과 같이 구해주었습니다.

 

def getFraction(numerator:list,dominator:list,dom):

    sumNumerator = 0

    for i in range(len(dominator)):
        sumNumerator += numerator[i] * (dom//dominator[i])
    return (sumNumerator,dom)

 

그 다음은 기약분수를 구하는 코드입니다.

 

7/3 의 분자를 15로 바꾸어주려면 분자에도 5를 곱하여 35/15를 만들어 주어야 합니다.

 

따라서 구해놓은 분모들의 최소공배수를 현재 분수의 분모로 나누어 몫을 구해준 다음 

 

몫을 분자의 값과 곱해준 값을 모두 더해주었습니다.

(이미 분모들의 최소 공배수는 앞에서 구해주어서, 분자들의 값의 합만 구하면 주어진 분수들의 합을 구할 수 있습니다.)

 

그런 다음, 최종 기약 분수의 분자 분모 값을 return 해주었습니다.

 

def DQ(num,x):
    if x == 1:
        return num
    tmp = DQ(num,x//2)
    if x % 2 == 1:
        return tmp *tmp* num % modular
    else:
        return tmp * tmp % modular

다음은 분할정복을 통해 값을 구하는 코드입니다.

 

sumN, lcd = getFraction(numerator,dominator,getLcd(dominator))

total = DQ(lcd,modular-2)

print((sumN*total) % modular)

 

최종적으로 값을 출력하는 부분입니다.

분수들의 값을 모두 더한 분자 분모를 구해줍니다.( sumN, lcd )

 

원하는 값은 lcd * (sumN ^  1000000005) mod  1000000007 이므로,

 

sumN ^  1000000005 mod  1000000007 값을 분할 정복으로 구해줍니다.

 

위에서 구한 값을 lcd 와 곱한 후  1000000007 로 나눈 나머지를 구해 출력해주면 됩니다.