[백준] #11050 - 이항계수 1

🔒문제 설명

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

입력

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

출력

$\binom{N}{K}$를 출력한다.

🔑해결 아이디어

이항계수 $\binom{N}{K}$를 구하는 공식은 $n! \over k!(n-k)!$로 어렵지 않습니다.
다만, 이 문제를 포스팅하게 된 것은 해당 문제가 DP 사용에 최적화 되어있기 때문입니다!
특정 입력에 대해 우리가 필요한 값은 $n!, k!, (n-k)!$으로 총 3개입니다. 이 중 $n!$을 구하는 과정에서 우리는 필연적으로 $k!$과 $(n-k)!$을 계산하게 됩니다. 따라서 DP 배열의 각 index DP\[i]에는 (i+1)!의 값을 저장 해 둠으로써 시간을 단축시켰습니다.

💻소스코드

import java.util.Scanner;  
  
public class BJ11050 {  
    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];  
        for(int i = 0; i<n; i++){  
            if(i == 0){  
                DP[i] = 1;  
            }  
            else  
                DP[i] = DP[i-1] * (i+1);  
        }  
        if(k == 0 || k == n)  
            System.out.println(1);  
        else            System.out.println(DP[n-1] / (DP[k-1] * DP[n-k-1]) );  
    }  
}