[백준(Baekjoon)] 2407. 조합

 

 

[백준(Baekjoon)] 2407. 조합

 

 

2407번: 조합

 

 

[입력]

 

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

 

 

[출력]

 

nCm을 출력한다.

 

 

[풀이]

 

재귀로 풀 수 있지만 이 경우엔 시간초과가 발생한다.

그래서 다이나믹 프로그래밍을 이용했다.

n과 m은 모두 100이하이다.

배열을 100으로 만들면 인덱스는 99까지 존재하기 때문에 배열을 더 편리하게 사용하기 위해 101로 설정하였다.

1C1과 1C0은 1이다.

그리고 10C1 은 10인데 이것은 9C1 + 9C9 와 같다.

즉 nCr = n-1Cr + n-1Cr-1 이다.

이 식을 사용하여 배열을 채워준다.

 

 

 

public class bj2407 {

	public static void main(String[] args) throws NumberFormatException, IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		String token[] = br.readLine().split(" ");
		int n = Integer.parseInt(token[0]);
		int m = Integer.parseInt(token[1]);
		
		BigInteger[][] dp = new BigInteger[101][101]; //범위에 해당하는 BigInteger배열
		
		dp[1][0] = dp[1][1] = BigInteger.ONE; //1C0 과 1C1은 모두 1
		for (int i = 0; i < 101; i++) {
			for (int j = 0; j <= i; j++) { //j는 i보다 클 수 없음. 2개중 3개뽑기 불가
				if(i == j || j == 0) {
					dp[i][j] = BigInteger.ONE;
				}
				else {
					dp[i][j] = dp[i-1][j].add(dp[i-1][j-1]); //nCr = n-1Cr + n-1Cr-1
				}
			}
		}
		System.out.println(dp[n][m]);
		
	}

}

 

 

메모리	시간	언어	코드 길이
14640	140	Java 11	769