[BOJ 11051] 이항 계수 2 (Java)

문제

https://www.acmicpc.net/problem/11051

11051번: 이항 계수 2

 

풀이

nCk 조합을 구한는 문제로 조합의 성질을 이용하여 재귀함수를 구현하여 풀 수 있다. 

(메모제이션 기법도 적용)

• nCn =1, nC0 = 1
• nCk = n-1Ck-1 + n-1Ck

 

소스코드

package math;

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

public class BOJ11051 {

    public static Integer memozation[][];
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        memozation = new Integer[1001][1001];
        System.out.println(combination(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())));
    }

    public static int combination(int n, int m){
        // nCm
        // nCm = n-1Cm-1 + n-1Cm
        if(n == m || m == 0) return 1;
        if(memozation[n][m] != null) return memozation[n][m];

        memozation[n][m] = (combination(n-1, m-1) + combination(n-1, m))%10007;
        return memozation[n][m]%10007;
    }
}