[백준] boj 2407 조합

코테 후,, 조합을 빠르게 계산하는 방법을 고민해보았다,,ㅠ

1. 재귀 => 너무 느림

2. 반복문

3. dp

---

조합 성공

 

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

2 초

128 MB

21031

7120

6145

39.160%

문제

nCm을 출력한다.

입력

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

출력

nCm을 출력한다.

예제 입력 1 복사

100 6

예제 출력 1 복사

1192052400

 

[코드]

package solved.Class;

import java.io.*;
import java.math.BigInteger;
import java.util.*;

public class Main {


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        String temp[] = br.readLine().split(" ");

        int n = Integer.parseInt(temp[0]);
        int m = Integer.parseInt(temp[1]);

//        BigInteger a  = comb_recursion(n,m);
        setDp(n,m);
        System.out.println(dp[n][m]);
    }

    //조합 반복문 - 수학 계산
    public static BigInteger comb_for(int n, int m){
        int t = n-m;
        BigInteger result = new BigInteger("1");

        for(int i=n;i>t;i--){
            result=result.multiply(BigInteger.valueOf(i));
        }

        for(int i=m; i>1 ; i--)
            result=result.divide(BigInteger.valueOf(i));

        return result;
    }

    //조합 개수 - 너무 느림
    public static BigInteger comb_recursion(int n, int r){
        if(n==r || r==0)
            return new BigInteger("1");
        return comb_recursion(n-1,r-1).add(comb_recursion(n-1,r));
    }

    //조합 동적계획 - dp

    public static BigInteger dp[][] = new BigInteger[1000][1000];

    public static void setDp(int n, int r){
        for(int i=1;i<=n; i++){
            for(int j=0;j<=i;j++){
                if(j==0||j==i)
                    dp[i][j] = new BigInteger("1");
                else
                    dp[i][j] = dp[i-1][j-1].add(dp[i-1][j]);
            }
        }
    }
}