백준 6591번 이항 쇼다운 :: 마이구미

이 글은 백준 알고리즘 문제 6591번 "이항 쇼다운" 을 풀이한다.

조합에 관련된 시리즈 문제 중 하나이다.

문제는 쉬워보이나 굉장히 낮은 정답 비율을 통해 만만치 않다는 것을 알 수 있다.

6591번 - https://www.acmicpc.net/problem/6591

n개의 원소 중에서 k개를 순서 없이 선택하는 방법의 수는 몇 가지 일까?

문제의 설명에서 조합의 정의에 대해 그대로 명시했기 때문에, 조합 문제인 것을 알 수 있다.

다른 관련 문제들은 단순한 접근 또는 동적계획법을 통해 해결할 수 있다.

하지만 이 문제는 다르게 접근해야한다.

우리는 실제로 수학 문제를 풀 때, 1번을 이용해서 조합 문제를 해결한다.

다음과 같이 풀 수 있다.

10C4 => (10*9*8*7) / (4*3*2*1)
10C3 => (10*9*8) / (3*2*1)

단순한 구현에 있어, 분자끼리 계산한 값을 분모끼리 계산한 값을 나누면 된다.

위와 같은 흐름을 구현하면 어떻게 되는가?

실제로 수학 문제를 풀면, 수가 커지면 커질수록 계산하기가 힘들다. ex) 12345*12344*12343,,,,,,,,

구현에 있어서도, 수가 너무 광범위하게 커져 타입의 범위를 어마어마하게 초과할 것이다.

실제로 수학 문제를 풀 때는 계산하기 쉽게 나눌 수 있는 것들 끼리는 나누는 방식으로 약분을 하면서 풀게 된다.

약분을 하면서 계산할 수 있다면, 문제를 해결할 수 있게 된다.

구현에 있어, 인접한 수의 개수(n)일 경우, n의 배수인 것을 활용한다.

9 * 8 * 7 * 6 * 5 = 15120 -> 5의 배수
9 * 8 * 7 * 6 = 3024 -> 4의 배수
9 * 8 * 7 = 504 -> 3의 배수
9 * 8 = 72 -> 2의 배수

하지만 시간 초과를 경험했다.

해결책은 위의 조합의 공식 중에서 3번을 이용하면 시간을 절약할 수 있게 된다.

// nCr == nCn-r
if (a - b < b) {
    b = a - b;
}

private void solve() {
    StringBuilder sb = new StringBuilder();
    while (true) {
        int a = sc.nextInt();
        int b = sc.nextInt();
        int div = 1;
        long ans = 1;
 
        if (a == 0 && b == 0) {
            break;
        }
 
        if (a - b < b) {
            b = a - b;
        }
 
        while (b-- > 0) {
            ans *= a--;
            ans /= div++;
        }
        sb.append(ans + "\n");
    }
    System.out.println(sb.toString());
}