[백준/BOJ] platinum5 - 11402번 이항 계수 4 (Python)

▶11402 - 이항 계수 4

▶문제

자연수 n과 정수 k가 주어졌을 때 이항 계수 nCk를 m으로 나눈 나머지를 구하는 프로그램을 작성하시오.

 

▶입력

첫째 줄에 n, k와 m이 주어진다. (1 ≤ n ≤ 10^18, 0 ≤ k ≤ n, 2 ≤ m ≤ 2,000, m은 소수)

 

▶출력

 nCk를 m으로 나눈 나머지를 출력한다.

 

▶예제

▶풀이

dp문제라고 해서 풀었는데 왜 dp인지는 잘 모르겠다.

이것도 dp에 포함되는 문제인가 보다. 아님 내가 dp를 쓰지 않고 풀었나 보다.

 

아무튼 어떻게 풀지 고민하면서 구글에 검색을 해보았는데

이항 계수를 구해서 m으로 나누는 문제는 '뤼카의 정리'를 사용하면 된다고 보았다.

 

그래서 뤼카의 정리가 뭔지 찾아보았다.

https://ko.wikipedia.org/wiki/%EB%A4%BC%EC%B9%B4%EC%9D%98_%EC%A0%95%EB%A6%AC

뤼카의 정리 - 위키백과, 우리 모두의 백과사전

간단하게 말하면 n과 k가 주어지는데

이를 m으로 나눈 나머지들을 리스트에 저장한다.

이때 반복문을 돌리면서 n, k는 m으로 나눈 몫으로 값을 변경해주고, 둘 중 하나가 0이 될 때까지 반복한다.

 

이렇게 구한 n, k리스트를 가지고 계산을 해주면 된다.

각각 i번째의 n, k의 값으로 nCk를 구하고 result에 곱해준다.

이때 result는 % m을 해준다.

 

이렇게 제출하면 정답이 나온다.

def calculation(n, k):
    if n < k:
        return 0
    elif n == k:
        return 1
    else:
        ans = 1
        for i in range(1, k+1):
            ans *= (n - i + 1)
            ans //= i
        return ans


n, k, m = map(int, input().split())
list_n = []
list_k = []

while n != 0 or k != 0:
    list_n.append(n % m)
    list_k.append(k % m)
    n //= m
    k //= m

result = 1
for i in range(len(list_n)):
    ni = list_n[i]
    ki = list_k[i]
    result *= calculation(ni, ki)
    result %= m

print(result)

플래티넘 문제라서 많이 고민을 하다가 검색을 해보았는데,

'뤼카의 정리'라고 너무 쉽게 풀 수 있는 방법이 있어서 놀랐다.

저번에도 생각이 들었는데, 역시 수학을 잘하면 프로그래밍도 잘할 수밖에 없나 보다.

나는 둘 다 못하니까 다른 사람들보다 노력을 더 많이 해야겠다.

플래 4문제를 푸니까 한 번에 7점이나 오른다.

하지만... 풀고 싶다고 풀 수 있는 플래 문제가 아니니까ㅜ 더 노력해야겠다.

 

 

👨‍💻 이 문제의 한줄평 : '뤼카의 정리'... 수학을 잘 알고 잘하면 코딩을 잘할 수 있다.