백준 - 조합(2407)

문제 출처

문제 출처 : 조합

문제 이해하기

N = 100, M = 6 경우일 때 nCm 를 수식으로 나타내어 결과값인 1192052400 를 출력하는 문제

주요 조건 이해하기 ⭐️

조합의 수식만 알면 문제 이해가 어렵지 않았을 것이다.

어떤 방법으로 풀지 먼저 생각을 해보자

조합 공식을 이용하여 N! / M!(N-M)! 공식으로 풀 수 있다. 하지만 N = 100, M = 50인 경우를 생각했을 때 long 타입보다 더 큰 자료형으로 데이터를 저장해야 한다. 그렇기 떄문에 BigInteger 클래스를 사용해야한다.

입출력 예시로 1192052400 를 도출하는 과정을 살펴보면

N! = 100 * 99 * 98 * 97 * 96 * 95 * 94 * ..... 6 * 5 * 4 * 3 * 2 * 1
M! = 6 * 5 * 4 * 3 * 2 * 1
(N-M)! = 94 * 93 * 92 * 91 * 90 * ....... 6 * 5 * 4 * 3 * 2 * 1

이렇게 나타낼 수 있다. 여기서 N!의 94이하의 팩토리얼은 (N-M)!과 동일한 값이고 약분이 가능해진다.

그렇기 때문에

100 * 99 * 98 * 97 * 96 * 95 / 6 * 5 * 4 * 3 * 2 * 1 

여기서 중요한 점은 long, double 타입으로 사용하게 되면 예제에 나와있는 테스트 케이스는 통과하겠지만, 제출시에는 틀릴 확률이 매우 높다.

제출 코드 (long 타입으로 사용한 경우)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class _2407_failed {

	static int N,M;

	private static long getNFactorial(long k) {
		if (k == (N - M) + 1) {
			return k;
		}
		return getNFactorial(k - 1) * k;
	}

	private static long getMFactorial(long k) {
		if (k == 1) {
			return 1;
		}
		return getMFactorial(k - 1) * k;
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");

		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());

		long result = getNFactorial(N) / getMFactorial(M);

		System.out.println(result);
	}
}

제출코드 (BigInteger 사용)

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

public class _2407_ {

	static BigInteger N,M;

	private static BigInteger getNFactorial(BigInteger n) {
		if (Objects.equals(n, N.subtract(M).add(BigInteger.ONE))) {
			return n;
		}
		return getNFactorial(n.subtract(BigInteger.ONE)).multiply(n);
	}

	private static BigInteger getMFactorial(BigInteger m) {
		if (Objects.equals(m, BigInteger.ONE)) {
			return BigInteger.ONE;
		}
		return getMFactorial(m.subtract(BigInteger.ONE)).multiply(m);
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");

		N = new BigInteger(st.nextToken());
		M = new BigInteger(st.nextToken());

		BigInteger result = getNFactorial(N).divide(getMFactorial(M));

		System.out.println(result);
	}

}

참고자료

큰 숫자(정수) 다루기 BigInteger 사용법 & 예제 총정리