백준 6591번: 이항 쇼다운 (C++)

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

6591번: 이항 쇼다운

---

Level: Silver III

Solved By: Math

 

4번의 솔루션에 풀 수 있었습니다.

1) nCr = n-1Cr + n-1Cr-1의 특성을 활용하여 Top-Down DP로 풀려했지만 메모리 초과로 실패했습니다.

2) 10!이 INT_MAX보다 작은 것을 고려하여 10까지의 factorial을 구해놓고 f[n]/(f[n-k]*f[k])로 풀려했지만 OutOfBound로 실패했습니다.

3) n!/(r!*(n-r)!)이 (n*(n-1)*...*(n-r+1))/r!임을 알고, [1] n*(n-1)*...*(n-r+1), [2]r!을 직접 구하여 [1]/[2]를 구했지만 overflow로 실패했습니다.

4) 1 이상의 자연수는 1씩 차이나는 인접한 수들이 N개의 곱으로 이루어져 있다면, N의 배수라는 Lemma를 알고 있다면 3)의 [1]/[2]를 동시에 구할 수 있습니다.

 

이를 증명한다면 1 * 2 * ... * N은 N이 포함되어있으므로 N의 배수가 맞습니다. 시작점이 어디라 하든 이는 성립하는 것을 확인할 수 있습니다. N - 3 * N - 2 * N - 1 * N * ... * 2N - 4에도 N은 포함되어있으므로 이 Lemma는 성립함을 알 수 있습니다.

 

하지만, 이를 코드로 구현하는 과정에서도 overflow가 날 수 있기 때문에 답을 출력하는 변수 자체를 long long으로 선언합니다. 어떤 변수인지는 코드에 주석을 통해 적어두었습니다.

#include <iostream>
using namespace std;

void swap(int* a, int* b){
    int* temp = a;
    a = b;
    b = temp;
}

int main(){
    while(true){
        int n, k; cin >> n >> k; if(!n && !k) break;
        int r = n - k;
        if(r > k) swap(r, k);
        
        int div = 1;
        long long ans = 1;
        for(int i = n; i >= n - r + 1; i--){
            ans *= i; // 여기서 overflow가 날 수 있어서 long long으로 선언
            ans /= div;
            div++;
        }
        
        cout << ans << '\n';
    }
    return 0;
}