[백준] 16565번. N포커(JAVA)

문제

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

---

풀이(50분)

import java.io.*;

public class Main {
    static final int MOD = 10007;
    static int[][] comb = new int[53][53];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int ans = 0;

        // 조합 초기화
        for (int i = 0; i <= 52; i++) {
            comb[i][0] = 1;
        }

        for (int i = 1; i <= 52; i++) {
            for (int j = 1; j <= 52; j++) {
                comb[i][j] = (comb[i - 1][j] + comb[i - 1][j - 1]) % MOD;
            }
        }

        for (int i = 1; i <= 13 && N - 4 * i >= 0; i++) {
            int temp = (comb[52 - 4 * i][N - 4 * i] * comb[13][i]) % MOD;

            if (i % 2 == 1) {
                ans = (ans + temp) % MOD;
            } else {
                ans = (ans - temp + MOD) % MOD;
            }
        }

        System.out.println(ans);
    }
}

---

문제 풀이 전략

 

nCi = nC(i-1) * (n - i + 1) / i 는 조합식을 통해 조합 값을 계산해두는 것이다.

13까지만 하는 이유는 같은 네장을 하나로 묶어서 볼 것이기 때문에 52/4를 한 셋트로 보는 것이다.

 

추가로 홀수인 경우에는 더하고, 짝수인 경우에는 뺴는 이유는 포함 배제의 원리와 같다.

중복되어 포함되는 부분을 제거함으로써 정확한 정답을 출력하는 것이다.

 

예를 들면, 1, 2, 3의 교집합에 대하여 중복을 제거하는 방식을 채택하는 것이다.