[Silver3-JAVA] 백준 2407 - 조합

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

2407번: 조합

 

 

🤔 문제풀이

처음 문제를 보고 재귀로 풀으려고 했다가 시간초과가 계속 나서 힘들었었던 문제다.

조합에 관련된 문제가 자주 나오므로 알고있으면 좋을 것 같다.

 

어떤 n과 m이 주어졌을때

nCm = (n-1)C(m) + (n-1)C(m-1)이다.

또한 nC0 = nCn = 1이며

nCm = nCn-m이다. (ex. 4C3 = 4C1)

 

데이터의 최대 범위를 입력했을 때 숫자가 매우 크게 나오기 때문에

무한대를 표현할 수 있는 class인 BigInteger을 사용했다.

BigInteger 형식의 데이터를 사칙연산하기 위해서는 연산에 해당하는 메서드를 사용해야되더라,

만약 몰랐다면 코딩테스트에서 활용하지 못했을 것이다. 잘 알아두도록 해야겠다.

 

🚨CODE

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

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		
		BigInteger[][] bi = new BigInteger[101][101];
		
		for(int i = 1; i<=n; i++) {
			for(int j = 0; j<=i; j++) {
				if(i==j || j==0)
					bi[i][j] = BigInteger.ONE; // 1
				else
					bi[i][j] = bi[i-1][j-1].add(bi[i-1][j]);
			}
		}
		
		System.out.println(bi[n][m]);
	}
}