백준 : 2407 : 조합 (DP)

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

2407번: 조합

이번문제는 조합을 구현하는 DP문제이다 이차원 배열을 사용하면 규칙을 쉽게 찾을 수 있다.

다만, 밑에 주의사항을 알아야 해결할 수 있다.

 

주의 : 숫자가 int,long 보다 커지기 때문에 BigInteger 사용해야함

사용법 :

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

  BigInteger.valueOf(i);

  BigInteger.ONE;

  dp[i][j] = dp[i-1][j].add(dp[i-1][j-1]);

 

점화식 : dp[i][j] = dp[i-1][j].add(dp[i-1][j-1]);

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

class Main {

	static int n, m;
	static BigInteger[][] dp;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		n = sc.nextInt();
		m = sc.nextInt();
		sc.nextLine(); // 버퍼
		
		dp = new BigInteger[n+1][n+1];

		// 입력
		for (int i = 1; i < n+1; i++) { //1부터 시작*****
			for (int j = 1; j <= i; j++) {

				if (j == 1) { // nC1은 무조건 n
					dp[i][j] = BigInteger.valueOf(i);
					continue;
				}

				if (i == j) { // nCk에서 n == k 같으면 무조건 1
					dp[i][j] = BigInteger.ONE;
				} else {
					dp[i][j] = dp[i-1][j].add(dp[i-1][j-1]);
				}
			}
		}

		System.out.println(dp[n][m]);

	}
}