BOJ) 이항 계수 2

이항 계수 2

11051번: 이항 계수 2

풀이

 

nCr 을 구하는 문제다.

nCr = n-1Cr-1 + n-1Cr 이라는 공식을 저번에 이어서, 다시 한번 머리에 남기기 위해 포스팅 한다.

r이 0일 때와, n일 때 1로 설정하고, 나머지 r에 대해서 위의 공식을 적용하면 된다.

 

 

코드

 

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

public 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());
        br.close();
        solution(n,k);
    }

    private static void solution(int n, int k) {
        int[][] dp = new int[n+1][n+1];
        final int mod = 10007;

        for(int i=1; i<=n; i++) {   // nCr = n-1Cr + n-1Cr-1
            dp[i][0] =1;
            dp[i][i] =1;
            for(int j=1; j<i; j++) {
                dp[i][j] = (dp[i-1][j-1] + dp[i-1][j])%mod;
            }
        }
        System.out.println(dp[n][k]);
    }
}