[BOF] 16134 : 조합(Combination) [G1]

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

16134번: 조합 (Combination)

 

 

 

[문제]

준하는 기초통계학 수업에서 너비가 a, 높이가 ​​​​​b인 격자판의 좌하단 점으로부터 우상단 점까지 최단경로로 가는 방법의 수를 구하라는 과제를 받았어.

알고 있겠지만 정답은 (a+b)Cb이야. 보기만 해도 벌써 조합을 계산할 생각에 신이 나지? 사실 조합을 구하는 문제도 코딩으로 해결할 수 있대. 코딩으로 과제를 해결해주자!

[입력]

첫 줄에 N과 R이 주어진다. (0 ≤ R ≤ N ≤ 1,000,000)

[출력]

 NCR 의 값을 1,000,000,007로 나눈 나머지를 출력하자! (단, 1,000,000,007은 소수이다)

서브태스크 1 (10점)

• N ≤ 10

서브태스크 2 (30점)

• N ≤ 30

서브태스크 3 (50점)

• N ≤ 1,000

서브태스크 4 (10점)

• 추가 제한 없음

 

[예제 입력 1]

4 2

[예제 출력 1]

6

 

[예제 입력 2]

30 15

[예제 출력 2]

155117520

 

 

 

[내 풀이]

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main_16134_조합 {

	static final int P = 1000000007;
	
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int R = Integer.parseInt(st.nextToken());
		
		// 페르마의 소정리와 모듈러 연산을 이용해 풀어보자
		long[] dp = new long[N+1];
		dp[0] = 1;
		// 모듈러 연산
		for (int i=1; i<N+1; i++) {
			dp[i] = (dp[i-1] * i) % P;
		}
		
		// 페르마의 소정리
		// dp[R] * dp[N-R] 때문에 long타입으로 선언해야함
		long multipleNum = fermat((dp[R] * dp[N-R]) % P, P-2);
		
		// 모듈러 연산
		System.out.println((dp[N] * multipleNum) % P);
		
	}
	
	static long fermat(long num, long idx) {
		if (idx == 1) return num;
		
		if (idx % 2 == 0) { // 짝수
			long temp = fermat(num, idx / 2);
			return (temp * temp) % P;
		}
		
		else { // 홀수
			long temp = fermat(num, idx - 1);
			return (temp * num) % P;
		}
	}

}

 

 

[회고]

<페르마의 소정리> 와 <모듈러 연산>을 이용하여 풀었습니다.

 

페르마의 소정리를 조합에서 응용해보자.

nCr = n! / r! * (n-r)!이다.

⇒ n! * (r! * (n-r)!)^-1

페르마의 소정리에 의해 nCr을 일정한 소수 p로 나눈 나머지를 구하라고 한다면

n! * (r! * (n-r)!)^-1 === n! * (r! * (n-r)!)^(p-2) (mod p)

이제 위식은 모두 곱셈으로 연결되어 있으므로 모듈러 연산이 가능하다!