본문 바로가기

카테고리 없음

[백준 11401번] 이항 계수 3 (Python3)

import sys
input = sys.stdin.readline
mod = 1000000007

N,K = map(int,input().split())

def cal(x,n):
  if n == 1:
    return x
  cal2 = cal(x,n//2)
  if n%2:
    return cal2*cal2*x %mod
  else:
    return cal2*cal2 %mod

numer = denom = 1
for i in range(1,K+1):
  numer = numer*(N+1-i) %mod
  denom = denom*(i) %mod
  
denom = cal(denom,mod-2)
print(numer*denom%mod)

 

처음에는 "뭐야 너무 단순한 문제 아니야?" 라고 생각했었다. 그러면서도 당연히 무지성 곱셈하는 문제는 아니겠지? 했는데 역시 아니었다.

그냥 단순 곱셈, 나눗셈을 해서는 절대 풀 수 없는 문제였다. 왜 틀렸는지를 알아봤더니, 나머지를 계산한 후 나누기 계산을 하는것이 문제였다. 예를 들어서 만약 N이 1000000008, K가 2인 경우 정답은 500000004이다. 그러나 mod연산을 하고 나눗셈을 해주면 1/2가 되는 것이다.

 

어떻게 해결해야 하지 고민하던 중에 이전에 시그마 문제를 풀었던 기억이 났다. [백준 13172번] Σ (Python3) (tistory.com) 문제 읽을때 멀미났었던 문제였는데, 역시 쓰임새가 많으니 이런 문제를 냈었던 거구나 하는 생각이 들었다.

 

 

페르마의 소정리를 이용하면 쉽게 해결할 수 있다.

 

1. 분모와 분자를 따로 계산해주고, mod값으로 나눈 나머지를 구한다.

2. 나눗셈 연산을 페르마의 소정리를 이용해서 한다.

3. 결과 출력

 

 

오늘의 교훈) 페르마의 소정리를 잘 활용하자