[백준11050번] 이항 계수 1

문제

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

입력

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

출력

(NK)를 출력한다.

예제 입력 1

5 2

예제 출력 1

10

나의 풀이

파스칼의 삼각형을 생각하고 2차원 배열을 만든 뒤 점화식을 세운 뒤 문제를 풀었다. 아래 식과 그림을 첨부하였다.

코드

import java.util.Scanner;

/**
 * 11050번 이항 계수 1
 */
public class Baeckjun11050 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();

        int[][] dp = new int[n+1][n+1];

        for (int i=0; i<=n; i++) {
            for (int j=0; j<=i; j++) {
                if (j==0 || i==j) dp[i][j] = 1;
                else dp[i][j] = dp[i-1][j-1] + dp[i-1][j];
            }
        }

        System.out.println(dp[n][k]);
    }
}