[백준] 동적 프로그래밍 - 11051번 이항 계수 2 (Java)

문제링크

11051번: 이항 계수 2

 

접근한 방법

• 동적 프로그래밍

---

풀이방법

처음에는 예를 들어, $_{5}C_{2}$를 구한다 했을 때

$_{4}C_{0}$을 가장 먼저 구한 다음 차례 차례 조합 공식에 맞추어 $_{5}C_{1}$을 구하고 마지막 최종값을 구하도록 짰는데 틀렸다...

결국... 다른 분들의 블로그 도움을 받았다 T^T

 

이 문제는 파스칼의 삼각형을 이용하는 문제였다. (된장...ㅎㅎㅎ 언제 배웠는지도 기억이 안나는 데.. 이 이론을 기억할리가 있나 ㅎㅎㅎㅎ) 

파스칼의 삼각형 이론 참조 링크

 

파스칼의 삼각형의 이론을 요약하여 예를 들면, 아래와 같다.

$_{5}C_{2}$ = $_{4}C_{1}$ + $_{4}C_{2}$

---

소스코드 작성 방법

• a를 2중 배열로 선언하며 크기를 [n+1][k+1]로 한다.
• 이중 반복문을 돌리며 i를 n, j를 k라하면
  i == j (n과 k가 같을 때), j == 0 (k가 0일 때) 값을 1로 저장
  e.g. $_{5}C_{5}$ = 1, $_{5}C_{2}$ = 1
• i > 0 일 때 파스칼의 삼각형 이론을 이용하여
  a[i][j] = a[i-1][j-1] + a[i-1][j] 로 선언한다.
• 마지막으로 10007 나머지를 저장

 

소스코드

package baekjoon.dp;
import java.io.*;
import java.util.StringTokenizer;

public class Q_11051_BinaryCoe {
    public static long solution(int n, int k){
        long a[][] = new long[n+1][k+1];

        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= k; j++) {
                if(i == j || j == 0)
                    a[i][j] = 1;
                else if (i > 0) {
                    a[i][j] = a[i - 1][j - 1] + a[i - 1][j];
                    a[i][j] %= 10007;
                }
            }
        }

        return a[n][k];

    }
    public static void main (String[] args) throws IOException {
        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 k = Integer.parseInt(st.nextToken());

        bw.write(solution(n,k)+"\n");

        br.close();
        bw.close();
    }
}