[백준] S3 2407번 조합 (JAVA)

문제 출처 - Baekjoon Online Judge

문제는 여기

2407번: 조합

[문제] 

nCm을 출력한다.

[입력]

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

[출력]

nCm을 출력한다.

 

 

---

[풀이]

1. 주어진 시간이 적기 때문에 dp로 풀었다.

2. long형의 범위를 벗어나기 때문에 BigInteger를 사용해야 한다.

[접근]

1. 시간이 부족하다고 생각해 long형의 dp 배열을 만들어서 문제를 풀었다.

2. 하지만 long형의 범위를 벗어나는 경우가 있어 어떻게 처리해야 하는지 고민하였다.

3. 검색을 통해 알아보니 long형의 범위를 벗어날 경우 BigInteger라는 형을 사용하면 해결할 수 있다고 하여 BigInteger를 사용해서 문제를 해결할 수 있었다.

[코드]

package BOJ_silver;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.util.StringTokenizer;

public class Main_S3_2407 {
	static BigInteger dp[][];
	static int n;
	static int m;
	
	public static void main(String[] args) throws Exception {
		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];
		
		// dp로 만드는 조합
		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]);
			}
		}
		
		System.out.println(dp[n][m]);
	}
}