[백준 16565] N포커

 

 수학에 기반한 문제이다. N이 최대 52까지 들어올 수 있으므로 완전 탐색과 백트래킹을 사용하는 것은 불가능하다. 러프하게 잡아도 52! 회의 탐색 과정이 필요하고, 최적화하더라도 52C26 회의 탐색은 필요하기 때문이다.

 

 처음에는 대수적으로 일반화시킬 수 있는 식이 존재하지 않을까 싶어서, 방정식을 찾으려 애쓰다가 그건 찾지 못해서 조합론을 사용하기로 했다. 구해야 하는 것은 플레이어가 이기는 수이므로, 그 조건인 포카드의 형성을 달성하는 조합만 찾아 모두 더하면 된다.

 가령 5장을 뽑았을 때, 플레이어가 이기는 수를 생각하자면 포카드 형성에 소모되는 4장을 제외하고 남은 모든 카드 중에 1장을 고르는 경우가 된다. 이때, 포카드가 A부터 K까지 13종류가 형성될 수 있으므로 결국 13 * 48C1이 될 것이다. 하지만 뽑는 카드의 수가 많아지는 경우에는 조금 달라진다. 만약 8장 이상을 뽑는 상황을 생각한다면, 포카드가 여러 쌍인 경우가 나타난다.

 위에서 단순하게 설명했던 방법으로 뽑는다면, 특정 포카드를 형성한 경우를 따지는 조합에 다른 포카드가 형성되는 경우가 포함되게 된다. 그렇다면 다른 포카드를 형성한 경우를 따지는 조합이 더해지는 과정에서 중복되는 경우의 수가 포함되어 버린다(그러니까 A포카드 조합에 A포카드와 2포카드를 보유하는 조합이 고려가 되는데, 2포카드 조합을 고려하는 과정에서 2포카드와 A포카드를 보유하는 조합이 다시 고려된다는 소리다).

 그래서 그 상태에서 중복으로 더해진 교집합을 빼준다. 단순하게 포카드 두 쌍에 8장을 소모한다고 치고, 나머지에서 남은 카드를 뽑는 경우를 계산해서 빼주면 된다. 이때 포카드 쌍은 A~K 까지 13종류 중 2가지를 고르는 경우이므로 13C2 * 나머지 조합이 될 것이다. 

 여기서 더 나아가 포카드를 세 쌍까지도 형성할 수 있는 N이라고 생각해 보면, 방금의 과정에서 포카드가 세 쌍인 경우들이 경우의 수에서 모두 빠져버렸음을 생각할 수 있다. 결국에는 N 값에 따라, 형성될 수 있는 포카드 쌍 수를 알아내 조합 값들을 더하고 빼고 가 계속 반복됨을 알 수 있다.

 

 나중에 풀고 나서 찾아보니, 저걸 포함-배제의 원리라고 하던데 굳이 그 개념을 몰라도 조합에 대한 직관만 있다면 충분히 도출할 수 있는 내용인 것 같다. 오히려 모듈러 연산을 적용하는 과정에서 조금 생각해보아야 할 것이 많아서 그쪽에서 더 고생했다. 위의 내용을 코드로 옮기면 아래와 같고, 나는 미리 구해둔 이항계수 값들을 재활용하는 형태로 사용했다.

#include<iostream>
#include <vector>
#define MOD 10007

using namespace std;

int dp[53][53]; //dp[i][j] iCj

void initComb() {
    for(int i=1; i<=52; i++) {
        dp[i][0] = dp[i][i] = 1;
        for(int j=0; j<=i/2; j++) {
            dp[i][i-j] = dp[i][j] = (dp[i-1][j-1] + dp[i-1][j]) % MOD;
        }
    }
}

int main() {
    int n;
    cin >> n;  
    dp[0][0] = 1;
    initComb();

    int result = 0;
    for(int i=1; i*4<=n; i++) {
        int num = dp[13][i];
        if(i%2==1) {
            result = (result + (dp[52-i*4][n-i*4] * num) % MOD) % MOD;
        } else {
            result = (result - (dp[52-i*4][n-i*4] * num) % MOD + MOD) % MOD;
        }
    }

    cout << result;
}