[JAVA] 백준 11050 조합 점화식

 

 

11050번: 이항 계수 1

문제

자연수 $N$과 정수 $K$가 주어졌을 때 이항 계수 $\binom{N}{K}$를 구하는 프로그램을 작성하시오.

풀이

📌 DP 배열 초기화

        // 1 <= N <= 10, 0 <= K <= N
        int[][] D = new int[11][11];

        for(int i=0; i<D.length; i++){
            // i개 중에서 i개를 뽑는 경우의 수는 1
            D[i][i] = 1;
            // i개 중에서 1개를 뽑는 경우의 수는 i
            D[i][1] = i;
            // i개 중에서 0개를 뽑는 경우의 수는 1
            D[i][0] = 1;
        }

N과 K가 10을 넘지 않으므로 0 ~ 10까지의 2차원 배열을 선언하였습니다.

• i개 중에서 i개를 뽑을 경우의 수는 i개
• i개 중에서 1개를 뽑을 경우의 수는 1개
• i개 중에서 0개를 뽑을 경우의 수는 1개

위의 경우를 바탕으로 DP 배열을 초기화하였습니다.

📌 점화식을 통해 배열 만들기

        for(int i=1; i<D.length; i++){
            for(int j=1; j<D.length; j++){
                // 조합의 점화식 i combination j = i-1 combination j-1 + i-1 combination j
                D[i][j] = D[i-1][j-1] + D[i-1][j];
            }
        }

• 조합의 점화식 i 콤비네이션 j = i-1 콤비네이션 j-1 + i-1 콤비네이션 j
• 위의 점화식을 토대로 배열을 채워주었습니다.

📌 전체 코드

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

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());

        // 1 <= N <= 10, 0 <= K <= N
        int[][] D = new int[11][11];

        for(int i=0; i<D.length; i++){
            // i개 중에서 i개를 뽑는 경우의 수는 1
            D[i][i] = 1;
            // i개 중에서 1개를 뽑는 경우의 수는 i
            D[i][1] = i;
            // i개 중에서 0개를 뽑는 경우의 수는 1
            D[i][0] = 1;
        }

        for(int i=1; i<D.length; i++){
            for(int j=1; j<D.length; j++){
                // 조합의 점화식 i combination j = i-1 combination j-1 + i-1 combination j
                D[i][j] = D[i-1][j-1] + D[i-1][j];
            }
        }
        System.out.println(D[N][K]);
    }

}

결과