[백준][Gold1]11401-이항계수3-JAVA
[문제]
11401번: 이항 계수 3
자연수 \(N\)과 정수 \(K\)가 주어졌을 때 이항 계수 \(\binom{N}{K}\)를 1,000,000,007로 나눈 나머지를 구하는 프로그램을 작성하시오.
www.acmicpc.net
[풀이]
1. 정수론에서의 합동
우리는 보통 합동이라는 단어를 도형의 합동을 얘기할 때 사용한다. 그런데 정수끼리의 관계를 얘기할 때도 합동이라는 개념이 존재한다.
정수론에서 합동은 어떤 개념일까?
A: 비행기가 13시에 출발한다고?
B: 응, 1시에 출발해
13과 1은 다른 숫자임에도 시각에서는 동일시된다. 우리가 쓰는 시계를 12시 단위이기 때문에 12로 나눈 나머지만 말해도 소통이 가능하다.
정수론에서도 마찬가지다.
정수 a, b를 m으로 나눈 나머지가 같을 때, a와 b는 m에 대하여 합동이라고 하며 표기는 다음과 같다.
∴ a ≡ b mod m
즉, 13 ≡ 1 mod 12
※ 합동에서는 정수만 다룬다. 0.3을 12로 나눈 나머지 따위는 생각하지 않는다.
2. 페르마의 소정리
페르마의 소정리란 "어떤 수가 소수일 간단한 필요조건에 대한 정리" 라고 하는데.. 아래 공식을 보자.
<페르마의 소정리>
P가 소수이고, a가 P로 나누어지지 않는 정수라면
a^P-1 ≡ 1 (mod P) 이다. 그리고 모든 a에 대하여
a^P ≡ a (mod P) 이다.
* 계산 예제
: 7^222 mod 11을 계산하라.
① 7보다 큰 소수 11을 이용해 페르마의 소정리를 적용해보면 다음과 같은 식을 얻을 수 있다.
7^11-1 ≡ 1 (mod 11)
7^10 ≡ 1 (mod 11)
② 7^222는 다음과 같다.
7^222 = 7^22×10 × 7^2
③ 따라서 답은
7^222 mod 11 = (7^22×10 × 7^2) mod 11
= ((7^10)*22 × 7^2) mod 11
= (1 mod11)*22 7^2) mod 11
= 1^22 7^2 mod 11
= 49 mod 11
= 5
※ 주의할 점: P가 소수이면 페르마의 소정리를 만족한다. 그러나 페르마의 소정리를 만족한다고 해서 모두 소수인 것은 아니다.
3. 페르마의 소정리로 이항계수 구하기
이항계수를 구하는 방법은 여러가지가 있다.
1) 이항계수 공식 이용하기
이항계수를 다음 공식이 성립한다.
그런데 만약 n이 커지면 nCr은 기하급수적으로 커져서 분명 문제에서 임의의 수 P로 나눈 값을 출력하라는 조건을 필연적으로 줄 것이다.
하지만 모듈러 연산은 나눗셈에 대해서는 성립하지 않기 때문에 이항계수 정의식에 적용할 수 없다.
(n!/r!(n-r)!) % P ≠ ((n! % P) × (r!(n-r)! % P)) % P
2) DP(memoization) 이용하기
이항계수 성질 nCr = n-1Cr-1 + n-1Cr를 이용하는 DP 방식이다.
이차원 배열과 인덱싱을 통한 메모이제이션 기법으로 풀면 O(n^2)의 시간복잡도로 이항계수를 구할 수 있다.
하지만 역시 n이 너무 크다면 시간 초과가 나게 된다.
3) 페르마의 소정리
1번 이항계수 공식을 이용하면 A(분자)/B(분모) 꼴이기 때문에 %P를 할때 모듈러 연산을 적용할 수 없었다.
페르마의 소정리는 A/B를 AX 꼴로 만들어 계산을 용이하게 한다.
우리는 앞에서 페르마의 소정리 공식을 정리했다.
a^P-1 ≡ 1 (mod P)
여기에 a를 한번 더 나누면 다음과 같다.
a^P-2 ≡ a^-1 (mod P)
위식을 이항계수와 연관지으면 아래의 식이 성립하게 된다.
nCr % P = (n!/r!(n-r)!)) % P
-> n! = A, r!(n-r)! = B
-> (A * B^-1) % P
-> ((A % P) * (B^P-2 % P)) % P
-> (A * B^P-2) % P
[code]
package com.algorithm.baekjoon.gold;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
public class Test08 {
public static long div = 1_000_000_007;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
long A = getFactorial(N);
long B = getFactorial(M) * getFactorial(N - M) % div;
long answer = ((A % div) * (getPow(B, div - 2))) % div;
bw.write(answer + "\n");
br.close();
bw.flush();
bw.close();
}
public static long getFactorial(long num) {
long answer = 1L;
while (num > 1) {
answer*=(num % div);
num--;
}
return answer;
}
public static long getPow(long a, long b) {
if(b == 1) {
return a % div;
}
long temp = getPow(a, b/2);
// 지수가 홀수라면
if(b % 2 == 1) {
return (((temp * temp) % div) * a) % div;
}
return (temp * temp) % div;
}
}