백준 16565 (C++) N포커

최초 업로드: 2025-08-06 09:08:29

최근 수정 시간: 2025-08-06 09:08:58

게시자: rlatjwls3333

카테고리: 백준

# [Gold II] N포커

[문제 링크](https://www.acmicpc.net/problem/16565)

## 문제 설명

정연이는 트럼프 카드 (Playing Card)로 할 수 있는 새로운 게임을 만들기로 결심했다.

우선 이 게임은 딜러와 플레이어가 1:1로 플레이한다. 그리고 플레이어는 놓여진 52장의 트럼프 카드에서 N장의 카드를 뽑는다. 뽑은 카드들로 "포카드 (four of a kind)" 족보를 만들 수 있다면 플레이어의 승리, 만들 수 없다면 딜러의 승리로 게임이 끝난다. 그러나 정연이는 아직 공정한 게임을 위한, 뽑는 카드의 수 N을 결정하지 못하였다.

정연이가 쉽게 결정을 내릴 수 있도록, N개의 카드를 뽑았을 때 플레이어가 이기는 경우의 수를 출력하는 프로그램을 작성해주자.

트럼프 카드는 다음과 같은 52장의 카드로 구성된다.

Figure: 트럼프 카드 (Playing Card)의 구성

문양 4개: ♥, ♠, ◆, ♣, 숫자 13개: A, 2, 3, 4, 5, 6, 7, 8, 9, 10, J, Q, K

총 4 x 13 = 52장

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

## 입력

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

## 출력

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

## 풀이
#### match(i)를 정확히 i개의 포카드가 형성이 되는 경우의 수라고 할 때
#### comb(13, 1) * comb(48, n-4) = match(1) + 2match(2) + 3match(3) + 4match(4) + ...
#### comb(13, 2) * comb(44, n-8) = match(2) + 3match(3) + 4match(4) + ...
#### comb(13, 3) * comb(40, n-12) = match(3) + 4match(4) + ...
#### 이러한 수식이 형성되어 1부터 n/4까지 홀수일 때는 더해주고, 짝수일 때는 빼주었다.
#### 조합수는 모듈로 곱셈의 역원을 이용하여 구해주었다.

``` c++
#include<bits/stdc++.h>
using namespace std;

const int MOD = 10'007;

int pow(int a, int b) {
    if(b==0) return 1;
    if(b==1) return a;

int ret = pow(a, b/2);
    if(b%2) return ret*ret%MOD*a%MOD;
    return ret*ret%MOD;
}

int comb(int n, int r) {
 int ret=1;
 for(int i=n;i>n-r;i--) ret = ret * i % MOD;
 for(int i=2;i<=r;i++) ret = ret * pow(i, MOD-2) % MOD;
 return ret;
}

int main() {
 ios::sync_with_stdio(0); cin.tie(0);
 int n; cin >> n;
 int sum=0;
 for(int i=1;i<=n/4;i++) {
 if(i%2) sum += comb(13, i) * comb(52-i*4, n-i*4) % MOD;
 else sum -= comb(13, i) * comb(52-i*4, n-i*4) % MOD;
 }
 cout << (sum+MOD*100) % MOD;
}
```