[BAEKJOON] 11051 이항 계수 2

문제 요약

• 알고리즘 분류: 조합,  동적계획법
• 난이도:  Silver3
• 문제내용:
  • 이항 계수( N K)를 10007로 나눈 나머지를 결과를 출력해라
• 사이트 주소: https://www.acmicpc.net/problem/11051

11051번: 이항 계수 2

문제풀이

  2가지 푸는 방법이 있다. 하나는 조합공식을 사용해서 푸는 방법과  동적계획법으로 푸는 방식이다.

 

조합 공식 사용 방법

위의 조합 공식으로 사용 하면 된다. 파이썬에서는 factorial 함수를 제공한다.

 

DP로 접근하는 방법

위 사진은 파스칼 삼각형이다. 파스칼 삼각형의 공식은 아래와 같이 정의 할수 있다.

수학 식으로 정리한다면 아래와 같이 정의 할수가 있다.

위 식처럼 (0, 0) ~ (N, P)를 코드로 옮기면 된다.

 

코드

Python

1. DP

N, K =  map(int, input().split())
dp = [[1] * (N + 1) for _ in range(N + 1)]

for i in range(2, N + 1):
    for j in range(1, i):
        dp[i][j] = (dp[i - 1][j] + dp[i - 1][j - 1]) % 10007

print(dp[N][K])

2. 수학식

from math import factorial

N, K =  map(int, input().split())
print(factorial(N) // (factorial(N-K) * factorial(K)) % 10007)

Java

자바는 factorial 함수 제공하지는 않는다. 귀찮아서 자바는 수학식으로 한 코드는 없다.

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

public class Main {

	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());
		int[][] dp = new int[N + 1][N + 1];
		dp[0][0] = 1;
		for(int i = 1; i <= N; i++) {
			dp[i][0] = 1;
			for(int j = 1; j <= i; j++) {
				dp[i][j] = (dp[i - 1][j] + dp[i - 1][j -1]) % 10007;
			}
		}
		
		System.out.println(dp[N][K]);
			
	}
	
}