문제
N과 M이 주어질 때 조합 C(N, M)의 값을 구하라. 결과가 매우 클 수 있다.
입력
첫째 줄에 N과 M이 주어진다 (5 이상 100 이하, M 이상 N 이하).
출력
C(N, M)의 값을 출력한다.
예제
| 입력 | 출력 |
|---|---|
100 6 | 1192052400 |
풀이
BigInteger를 사용하여 C(N, M) = N! / (M! * (N-M)!)를 직접 계산한다.
- 분자: N * (N-1) * ... * (N-M+1)을 BigInteger로 누적 곱한다
- 분모: 1 * 2 * ... * M을 BigInteger로 누적 곱한다
- 분자를 분모로 나누어 결과를 출력한다
핵심 아이디어: BigInteger를 사용하면 오버플로우 없이 큰 수 연산이 가능하며, C(N,M) = N!/(M!(N-M)!)에서 분자와 분모를 각각 M번 곱한 후 나누면 된다.
코드
package day499;
import java.io.*;
import java.math.*;
public class Day478BOJ2407조합 {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] input = br.readLine().split(" ");
int n = Integer.parseInt(input[0]);
int m = Integer.parseInt(input[1]);
BigInteger sum = BigInteger.ONE;
BigInteger div = BigInteger.ONE;
for (int i = 0; i < m; i++) {
sum = sum.multiply(new BigInteger(String.valueOf(n - i)));
div = div.multiply(new BigInteger(String.valueOf(i + 1)));
}
System.out.println(sum.divide(div));
}
}복잡도
- 시간: O(M)
- 공간: O(1)