[JAVA] 백준 2407번 : 조합

 

 

---

 

• 생각

 nCm이 뭐였는지 기억이 잘 나지않아서 풀어보게 되었다.  nCm => n! / (n-m)!m! 라고 보면 된다.

 

1. 재귀로 풀어질 것 같다.(long타입으로도 범위를 받아들일 수 없다고함. ==>> BIgInteger 사용 해야함) ==>> 시간 초과

 

 

• 코드

정답 코드 : 핵심은 long타입도 범위를 받아들일 수 없기 때문에 BigInteger을 사용하는 것이다. 

 

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

public class Main {
	static int N, M;

	public static void main(String[] args) throws Exception {
		SetData();
		System.out.println(Combination());
	}

	private static void SetData() 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());
	}

	private static BigInteger Combination() {
		BigInteger num1 = BigInteger.ONE;
		BigInteger num2 = BigInteger.ONE;
		for (int i = 0; i < M; i++) {
			num1 = num1.multiply(new BigInteger(String.valueOf(N - i)));
			num2 = num2.multiply(new BigInteger(String.valueOf(i + 1)));
		}

		return num1.divide(num2);
	}
}