[백준 16565번] 파이썬 - N포커

백준 16565 - N포커

시간 제한 1초, 메모리 제한 256MB

# 조건

• 정연이는 트럼프 카드 (Playing Card)로 할 수 있는 새로운 게임을 만들기로 결심했다.
• 우선 이 게임은 딜러와 플레이어가 1:1로 플레이한다.
• 그리고 플레이어는 놓여진 52장의 트럼프 카드에서 N장의 카드를 뽑는다.
• 뽑은 카드들로 "포카드 (four of a kind)" 족보를 만들 수 있다면 플레이어의 승리, 만들 수 없다면 딜러의 승리로 게임이 끝난다.
• 그러나 정연이는 아직 공정한 게임을 위한, 뽑는 카드의 수 N을 결정하지 못하였다.
• 정연이가 쉽게 결정을 내릴 수 있도록, N개의 카드를 뽑았을 때 플레이어가 이기는 경우의 수를 출력하는 프로그램을 작성해주자.
• 트럼프 카드는 다음과 같은 52장의 카드로 구성된다.

• 포카드 (four of a kind)는 뽑은 N장의 카드 중에 "같은 숫자를 가진, 다른 문양의 4장의 카드"가 존재하는 경우를 의미한다.
• 또한 플레이어가 이기는 경우의 수는 N장의 카드에 이러한 카드 조합을 1쌍 이상 포함하고 있는 경우의 수를 의미한다.

입력

• 첫째 줄에 뽑는 카드의 수 N이 주어진다. (1 ≤ N ≤ 52)

출력

• 첫째 줄에 N장의 카드를 뽑았을 때, 플레이어가 이기는 경우의 수를 10,007로 나눈 나머지를 출력하라.

# 접근 방법

• 규칙을 찾기 위해 여러 방법을 시도하였다.
• 우선 4~7장의 카드를 뽑는 경우 포카드는 단 1종류만 손에 들고 있다.
• 하지만 8장을 넘어가는 순간 포카드 2종류 또는 3종류를 손에 들고 있는 경우의 수를 중복되어 카운트 하는 것을 발견하였다.
  • 예를 들면 8장의 카드를 뽑을 때
  • 1을 4장 들고 있는 상태에서 나머지 48장 중 4 장을 뽑는 경우와,
  • 2를 4장 들고있는 상태에서 나머지 48장 중 4장을 뽑는 경우,
  • 1 포카드와 2 포카드를 들고 있는 경우의 수는 중복되어 카운트 된다.
• 이 떄, 포함 - 배제의 원리를 사용하면 된다.

• 즉, 한 종류를 포카드한 경우 - 두 종류를 포카드한경우 + 3종류 - 4종류 .. 로 계산해주면 된다.
• n개를 뽑아 i 종류를 포카드하는 경우의 수는 13 C i
• 나머지 카드를 뽑는 경우는 52 - 4i C n - 4i 이다.
• 따라서 전체 식은 13Ci * (52-4i)C(n-4i) 이다.
  • 위의 식을 홀, 짝에 맞춰 홀수인 경우 더해주고, 짝수인 경우 빼주면 된다.
• 또한 itertools의 combination을 사용하면 list로 모든 조합이 나오지만, math의 comb를 사용해주면 조합의 수를 알려주므로 math의 comb를 사용해준다.

import sys  
sys.stdin = open('input.txt')  
input = sys.stdin.readline  
from math import comb  

N = int(input())  
mod = 10007  
answer = 0  

for i in range(1, N//4+1):  
    val = (comb(13, i)*comb(52-(4*i), N-(4*i)))  
    if i % 2:  
        answer += val % mod  
    else:  
        answer -= val % mod  


print(answer % mod)