백준)Q.11051_이항 계수 2(파스칼의 삼각형)

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

11051번: 이항 계수 2

문제

자연수 N과 정수 K가 주어졌을 때 이항 계수 (NK)를 10,007로 나눈 나머지를 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ K ≤ N)

 

출력

(NK)를 10,007로 나눈 나머지를 출력한다.

 

예제 입력 1 

5 2

 

예제 출력 1 

10

 

< 나의 풀이 >

import java.util.Scanner;
 
public class Q_11051 {
 
    public static void main(String[] args) {
 
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        long[][] bino = new long[n+1][k+1];
        for(int i=0;i<bino.length;i++) { // i = n
            for(int j=0;j<=i;j++) {  // j = k 
                if(j>k)
                    continue;
                else if(j==0 || i==j) 
                    bino[i][j]=1;
                else 
                    bino[i][j]=(((long)bino[i-1][j]+(long)bino[i-1][j-1])%10007);
            }
        }        
        System.out.println(bino[n][k]);
    }
}
 

 

파스칼의 삼각형을 이용해 풀었다. 이것 저것 해보았지만 제일 간단한 풀이법이다.

이항계수가 뭔지, 파스칼의 삼각형이 뭔지 알고싶지도 않고 복잡한게 싫어 외면하고 싶었지만 다른 방도가 없었다.

ㅠㅠ 

 

이항계수에 대해 간단히 설명하자면

예를들어 5C2이라고 했을때 5개의 수 중에 2개의 수를 고르는 경우가 몇가지냐...이건데 여기서 중복은 제외한다.

(ex. [1,5]와 [5,1]은 중복이므로 1가지 경우로 인정] 

식으로는 

이렇게 표현할 수 있다. 

 

어찌됐든 요점은,

이항계수 nCk는 파스칼의 삼각형으로 도식화 할 수 있다. 

그림의 ex1)을 보면 

5C3은 4C3과 4C2를 더한 값이고, 

ex2)의 3C1은 2C1과 2C0을 더한 값이다. 

 

결국 nCk = (n-1)Ck + (n-1)C(k-1)의 식을 도출해 낼 수 있고

이를 표로 정리하면 아래와 같다.

이 표대로 코딩해주면 되고 결과는 10,007을 나눈 나머지값이니까 애초에 나머지값을 넣기로 했다. 

 

for(int i=0;i<bino.length;i++) { // i = n

for(int j=0;j<=i;j++) { // j = k

if(j>k)

continue;

else if(j==0 || i==j)

bino[i][j]=1;

else

bino[i][j]=(((long)bino[i-1][j]+(long)bino[i-1][j-1])%10007);

}

}

j는 최대 I까지 증가하게 구현했다.

if : k이상의 j값은 필요하지 않으므로 j가 k보다 커질때는 그냥 continue해주고,

else if : j가 0일 경우 무조건 1이니 1을 넣고 

else : 그 외의 경우는 nCk = (n-1)Ck + (n-1)C(k-1) 요로코롬 해주고 10,0007을 나눈 값의 나머지를 넣는다.