[백준] 2407 조합 - DP JAVA

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

2407번: 조합

코드설명

DP 문제입니다.

 

파스칼의 삼각형을 활용하는 문제입니다.

파스칼의 삼각형에 의하여 nCm = n-1Cm-1 + n-1Cm 입니다.

 

이 문제에서 처음에 실수했던점은,

아래의 코드에서 for(int j=1;j<=101;) 로 처리하여 오류가 있었습니다.

nC0 부터 nCn 까지 처리해야하므로 아래의 코드처럼 for(int j=0;j<=i;) 로 처리합니다.

for(int i=1;i<101;i++) {
    for(int j=0;j<=i;j++) {
        if( j == 0) dp[i][j] = new BigInteger("1");
        else if( i == j) dp[i][j] = new BigInteger("1");

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

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.util.*;

public class Main {
	public static int T, N, M;
	public static int answer = 0;
	public static int[] arr;
	public static BigInteger[][] dp;
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	N = Integer.parseInt(st.nextToken());
    	M = Integer.parseInt(st.nextToken());
    	
    	dp = new BigInteger[101][101];
    	
    	for(int i=1;i<101;i++) {
    		for(int j=0;j<=i;j++) {
    			if( j == 0) dp[i][j] = new BigInteger("1");
    			else if( i == j) dp[i][j] = new BigInteger("1");
    			
    			else dp[i][j] = dp[i-1][j-1].add(dp[i-1][j]);
    		}
    	}
    	
    	System.out.println(dp[N][M]);
    }
    
}