백준 2407번 조합 (java)

[Silver III] 조합 - 2407

문제 링크

성능 요약

메모리: 14468 KB, 시간: 104 ms

분류

임의 정밀도 / 큰 수 연산, 조합론, 수학

제출 일자

2024년 9월 5일 03:27:13

문제 설명

nCm을 출력한다.

입력

n과 m이 주어진다. (5 ≤ n ≤ 100, 5 ≤ m ≤ 100, m ≤ n)

출력

nCm을 출력한다.

풀이

간단하게 조합을 구하는 구하는 문제다.

 

팩토리얼을 통해 구할 수도 있지만, 다이나믹 프로그래밍으로 풀어보겠다.

 

조합의 성질을 통해 nCr = n-1Cr + n-1Cr-1 이 된다.

 

참고로 32bit를 넘어가기 때문에 BigInteger를 사용해야 테스트케이스를 전부 통과할 수 있다.

전체 코드

public class Main {
    static int n=0,r=0;
    static BigInteger dp[][];
    public static void main(String args[])throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st  = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        r = Integer.parseInt(st.nextToken());

        dp = new BigInteger[n+1][r+1];

        bw.write(combi(n,r) + "");
        bw.flush();

    }
    static BigInteger combi(int n, int r){
        if(dp[n][r] == null) {
            if (n == r || r == 0) {
                return dp[n][r] = BigInteger.valueOf(1);
            }
            return dp[n][r] = combi(n - 1, r).add(combi(n - 1, r - 1));
        }
        return dp[n][r];
    }
}