[백준/16565] N포커 (Python)

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

16565번: N포커

 

Difficulty : Gold 2

 

Status : Solved

 

Time : 00:11:26

 

---

 

문제 설명

 

정연이는 트럼프 카드 (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

 

출력 예시

 

13

 

 

---

 

풀이

 

우선, 가장 기본적인 4 <= N < 8인 경우부터 시작해 보자. 승리할 경우의 수는 (포카드 13쌍 중 1쌍을 뽑을 경우의 수) x (52 - 4장 중 남은 N-4장을 뽑을 경우의 수)가 될 것이다. 이들 모두는 조합을 통해 빠르게 계산할 수 있다.

 

이제는 8장부터이다. 승리할 경우의 수는 두 가지 경우로 늘어난다. 포카드 한 쌍을 뽑을 경우의 수와, 포카드 두 쌍을 뽑을 경우의 수. 이 때, 포카드 한 쌍을 뽑을 경우의 수를 먼저 구하면 두 쌍을 뽑을 경우의 수가 중복 계산된다. 즉 이들을 빼주어야 한다.

 

12장부터는? 두 쌍을 뽑을 경우의 수와 더불어, 세 쌍을 뽑을 경우의 수 역시 고려해야 한다. 이 때는 두 쌍을 뽑을 경우의 수를 제거하면서 세 쌍을 뽑을 경우의 수가 제거된다. 즉 이들을 더해주어야 한다.

 

이런 식으로 반복하여 덧셈 - 뺄셈을 이어나가는 포함 배제의 원리를 적용하자. 만약 N장이 주어진다면

 

• 초기 쌍 pair = 1이고, 일반항은 (-1)^(pair-1) * Comb(13, pair) * Comb(52 - 4*pair, N-4*pair)이다.
• N-4*pair가 0보다 크거나 같을 때까지, 그리고 pair가 13보다 작을 때까지 모든 항을 더해주면 된다.

 

풀이 코드

MOD = 10007
N = int(input())

comb = [[0]*53 for _ in range(53)]
comb[0][0] = comb[1][0] = comb[1][1] = 1
for i in range(2, 53) :
  comb[i][0] = comb[i][i] = 1
  for j in range(1, i) :
    comb[i][j] = comb[i-1][j] + comb[i-1][j-1]
result = 0
cnt, pos = 1, 1
while N >= 4 :
  result += pos * comb[13][cnt] * comb[52-cnt*4][N-4]
  cnt += 1
  pos = -pos
  N -= 4

print(result % MOD)

풀이 완료!