[백준] 16134_조합 (Combination)

😄 개요

이 문제는 ${nCr}$ 을 구하라는 문제입니다.
다만 n과 r의 범위가 1,000,000 까지라 깡으로 계산하기에는 숫자가 어마어마하게 크다는 문제가 있죠.

물론 1,000,000,007로 나눈 나머지를 구하라고 하지만,
${nCr}$을 구하는 과정에서 나눗셈이 들어가서 선뜻 모듈러 연산을 중간 중간에 끼워 넣기에는 쉽지 않습니다.

이를 해결하기 위해 페르마의 소정리를 이용해 나눗셈을 곱셈으로 바꾸어 계산합니다.

---

🪡 로직

$nCr$

먼저, $nCr$ 부터 살펴봅시다.

분쟈의 $n!$ 의 일부와 분모의 $(n-k)!$ 를 날리면 결과적으로
${ (n - k + 1) * (n - k + 2) * ... *(n)}$ 에다가 $k!$을 나눠주면 됩니다.

페르마의 소정리

문제는 ${ (n - k + 1) * (n - k + 2) * ... *(n)}$ 이 어마어마하게 클 수 있어
중간중간에 모듈러 연산을 하며 계산을 이어나가줘야 하지만,
모듈러 연산을 한 분자에 $k!$로 나누면 결과가 바뀌어 함부로 중간 중간에 모듈러 연산을 할 수 없죠.

이를 해결하기 위해 페르마의 소정리를 이용합니다.
페르마의 소정리에 대한 자세한 내용은 이전 포스팅을 참고하세요.

결과적으로,
${(((n - k + 1) * (n - k + 2) * ... *(n)) * (k!)^{1,000,000,007 - 2})\ \ mod\ \ 1,000,000,007}$
를 구하면 됩니다.

하나의 식으로 적어놔서 괜히 어려워 보일 수 있지만,

n - k + 1 부터 n까지 곱하고,
거기에 k!의 1,000,000,005 거듭제곱을 곱하면 됩니다.
이 중간중간에 1,000,000,007으로 모듈려 연산도 해주고요.

---

🧵 코드

분자 계산하기

먼저 분자를 계산해줍니다.

numerator = 1
for i in range(N - R + 1, N + 1, 1):
  numerator = (numerator * i) % p

$N-R+1$부터 $N$까지 곱해주며 중간 중간에 p로 모듈러 해줬습니다.
간단하죠?

분모 계산하기

다음은 분모를 계산해줍니다.

denominator = 1
for i in range(1, R + 1):
  denominator = (denominator * i) % p

분모는 그냥 $k!$ 입니다. 역시 중간 중간에 p로 모듈러 해줬습니다.
더 간단하죠?

분모의 역원 구하기

분모의 p-2 거듭제곱을 구해줍니다.

invol = p-2
result = 1

while invol > 0:
  if invol % 2 == 1:
    result = (result * denominator) % p
  denominator = (denominator * denominator) % p
  invol = invol // 2

invol을 2로 나눠줘가고, 동시에 denominator을 제곱해줘가며
현재 거듭제곱을 곱해야할 때 result에 곱해주는 방식입니다.
이전 포스팅을 살짝 변형했습니다.

최종

이제 입력받고, 마지막에 분자와 분모의 역원을 곱해주기만 하면 됩니다.

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

p = 1000000007

#분자 계산하기
numerator = 1
for i in range(N - R + 1, N + 1, 1):
  numerator = (numerator * i) % p

#분모 계산하기
denominator = 1
for i in range(1, R + 1):
  denominator = (denominator * i) % p

#분모의 p-2 거듭제곱 구하기
invol = p-2
result = 1
while invol > 0:
  if invol % 2 == 1:
    result = (result * denominator) % p
  denominator = (denominator * denominator) % p
  invol = invol // 2

print((numerator * result) % p)

끝!

---

🐈‍⬛ 번외

사실 이 문제에 대해 공부하다가 발견한건데... 파이썬에선 $a^b \ mod \ p$ 를 열심히 비트연산해가며 거듭제곱 할 필요가 없더라구요...?

pow 함수의 세번째 인자를 넣으면 해당 인자로 모듈러 연산을 해준다고 합니다. 그리고 내부적으로 $a^b$를 구할때도 무식하게 $a$를 $b$번 곱하지 않는 듯 해요.

한마디로 요약하면,
분모의 p-2 거듭제곱을 구할 때

...
result = pow(denominator, p-2, p)
...

로 간략하게 줄일 수 있습니다. 앞으로는 자주 써먹어야겠어요😊

---

🔗참고

[알고리즘] 모듈러 연산과 나눗셈
[알고리즘] 분할정복으로 거듭제곱 빠르게 하기