문제링크
문제
정연이는 트럼프 카드 (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)
풀이 유형
풀이
조합을 생각해서 풀어야 하는 문제다. 파스칼의 삼각형을 이용하여 dp처럼 조합을 쌓아서 미리 저장해두고 사용해야 한다.
1
nCk[n][k] = nCk[n-1][k-1] + nCk[n-1][k];
생각을 해보자, 우리는 포카드 족보를 만들어야 한다. 총 숫자는 13 종류, 즉 순수한 포카드는 13종이다. 만약 우리가 뽑는 카드의 수 N이 15라고 한다면, 포카드가 수중에 1종류, 2종류, 3종류가 들어올 수 있다. 막연하게 생각하면, 아래와 같이 생각할 수 있다.
1
anw = nCk[13][i] * nCk[52-4*i][N-4*i];
13종의 숫자 중에서 i개 만큼을 고르고, 나머지 카드 뭉치에서 부족한 수의 카드를 뽑는다. 그러나 이 경우 우리는 중복 된 조합을 같이 카운트하게 된다. 그렇기에 우리는 중복된 쌍을 제거해야한다.
1종류의 조합을 구한다. 2종류의 조합이 중복되어 해당 부분을 제거한다. 제거하고 보니, 3종류의 조합이 같이 제거 되었다. 3종류의 조합을 추가한다. 추가하니 4종류의 조합이 같이 제거 되었다. 4종류의 조합을 추가한다. …. Etc
이와 같은 방식으로 포함 배제의 원리를 따라, 더해주고 빼주고를 반복하면 값을 구할 수 있다.
마무리
조합론인데, 말로 풀어 쓰려니 어렵다. 사실 단순히 더해주고 빼주고가 아닌데.. 나중에 정리가 되면 조금 더 자세히 적어보도록 하겠다.
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <iostream>
#define mod 10007
using namespace std;
int nCk[53][53];
int main(void){
ios::sync_with_stdio(false); cin.tie(NULL);
int N; cin>>N;
for(int n=0; n <= 52; n++){
nCk[n][0] = 1; nCk[n][n] = 1;
for(int k = 1; k < n; k++){
nCk[n][k] = nCk[n-1][k-1] + nCk[n-1][k];
nCk[n][k] %= mod;
nCk[n][n-k] = nCk[n][k];
}
}
int anw = 0;
for(int i=4; i<=N; i+=4){
if( (i/4) % 2 == 1){
anw += nCk[13][i/4] * nCk[52-i][N-i];
}
else{
anw -= nCk[13][i/4] * nCk[52-i][N-i];
}
anw %= 10007;
}
if(anw < 0) anw += mod;
cout<<anw<<endl;
}