백준 16565번 : N포커 [자바]

 

🧫 문제 분석

 

✔️ 출처

N포커 골드 2

 

📖 문제

 

포함 배제 원리에 대해 배우게 되었다.

 

 

말그대로 여러 집합을 합칠때 중복을 빼는 것이다.

 

짝수 집합일 경우 빼주고

홀수 집합일 경우 더한다.

세 집합 A,B,CA, B, CA,B,C 면:

출처 : 위키백과

→ 더하고 빼고 반복.

 

벤다이어그램으로 봤을때

2번째 짝수번째 빼기를 보면

3번 빼서 AnBnC가 없어진다

따라서 세 집합의 교집합을 더한다. 

 

최종적으로 중복ㅇ벗는 하나의 영역만 계산된다.

|B| + |C| + |D|

 

이경우 BnC가 2개

AnB 2개

AnC 2개

 

때문에 1개씩 빼줌

 

하지만 이러면 AnBnC가 사라짐

AnBnC 더함

 

최종적으로 중복없는 합 집합 생성 

---

🔅 문제 풀이

import java.io.*;
import java.sql.SQLOutput;
import java.util.*;

public class Main {

    static final long MOD = 10_007;
    // 계산은 long
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        // 4카드 이하면 이길 수 없음
        if (n < 4) {
            System.out.println(0);
            return;
        }

        int[][] dp = new int[53][53];

		// dp로 조합의 개수 미리 구해놓기
        dp[0][0] = 1;
        for (int i = 1; i < 53; i++) {
            dp[i][1] = i;
            dp[i][0] = dp[i][i] = 1;
            for (int j = 2; j < i; j++) {
                dp[i][j] = (int) ((dp[i - 1][j] + dp[i - 1][j - 1]) % MOD);
            }
        }

        long ans = 0;
        int max = n / 4;  // 가능한 최대 포카드 쌍 개수

        for (int i = 1; i <= max; i++) {
            // i쌍의 포카드를 뽑는 경우의 수
            long pickFourCard = dp[13][i];                   // C(13, i)
            long rest  = dp[52 - 4*i][n - 4*i];              // C(52 - 4*i, N - 4*i)
            long cnt = (pickFourCard * rest) % MOD;

            // 뽑은 포카드의 쌍의 수가 홀수일때는 더하고, 짝수일떄는 뺀다.
            if (i % 2 == 1) {
                ans = (ans + cnt) % MOD;
            } else {
                ans = (ans - cnt + MOD) % MOD;
            }
        }

        System.out.println(ans);

    }

}

 

 

 

❗ 오답노트 / 필요한 지식

1.  어렵다..
2.