110501

 

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main{
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String [] input = br.readLine().split(" ");
        
        int N = Integer.parseInt(input[0]);
        int K = Integer.parseInt(input[1]);
        
        int D[][] = new int[N+1][N+1];
        for(int i = 0; i < N+1; i++){
            D[i][0] = 1; D[i][i] = 1;
            for(int j = 1; j < i; j++){
                D[i][j] = (D[i-1][j-1]+D[i-1][j])%10007;
            } 
        }
        
        System.out.println(D[N][K]);
    }
}

 

문제 포인트

1. 다이나믹 프로그래밍

이항계수는 다이나믹 프로그래밍의 대표적인 예시이다.

nCk = n! / {(n-k)! *k!} 공식을 사용하여 구할 수도 있지만 파스칼의 삼각형을 적용하여 다이나믹프로그래밍으로 계산하는 방법도 있다.

 

1.이차원 배열 D[n][k] 에 nCk의 값을 넣고

2. for문을 돌며 nCk = n-1Ck-1 + n-1Ck 공식 적용

와 같은 코드를 통해 쉽게 구할 수 있다.

 

이 문제에서 후자의 방법이 사용된 이유는 뒤에 설명하겠다.

출처: 위키백과

2. Mod(나머지) 연산

Mod연산은 대게 정답이 자료형의 범위를 넘어가는 경우 값의 크기를 줄이기 위해 사용된다. 여기서 주의해야 할 점은 답을 구하는 과정에서도 값이 범위를 넘어갈 수 있다는 것이다. 이를 해결하기 위한 방법은 간단하다. Mod연산을 답을 구하는 중간 단계에서도 실행하는 것이다. 

 

(A + B) % C = {(A % C) + (A % B)} % C

(A x B) % C = {(A % C) x (A % B)} % C

(A - B) % C = {(A - C) + (A - B)} % C

 

Mod는 위와 같이 분배법칙(정확한 용어는 아니지만 편의상 이렇게 부르겠다) 이 성립하기 때문에  반복되는 연산일 경우 각 단계마다 Mod연산을 실행해도 올바른 답을 도출할 수 있음.

 

 

오답 노트

다이나믹프로그래밍이 아닌 nCk = n! / {(n-k)! *k!} 공식을 적용하여 문제를 풀었지만 오답이 나왔다. 

 

nCk

= (n-0)x(n-1)x...x(n-k+1) / k!

= {(n-0)/(k-0)} x {(n-1)/k-1} x ...x {(n-k+1)/1}

 

for 문을 돌려 순차적으로 {(n-i)/(k-i)} % 10007 을 계산하였다.

오답의 이유는 for문의 각 단계에서 {(n-i)/(k-i)} 값이 소수가 나올 수도 있다는게 원인이었다.

다이나믹 프로그래밍을 적용한 경우 각 단계에선 무조건 정수가 나오기에 Mod연산을 해도 정수 값이 나온다.

 

//틀린 코드
import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main{
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String [] input = br.readLine().split(" ");
        
        int N = Integer.parseInt(input[0]);
        int K = Integer.parseInt(input[1]);
    
        int a = 1;
        for(; K>0 ;){
           a =  (N/K % 10007) * a; 
           --N; --K;
        }
        System.out.println(a % 10007);
    }
}

 

 

정리

다이나믹프로그래밍(파스칼의 삼각형) 기법을 사용해 for문의 각 단계에서 정수 값을 구하고 Mod를 적용해 값이 커지는걸 방지한다.