[백준 16565] N포커

 

사실 평범한 dp문제라고 보고 쉽게 풀었는데 인터넷 풀이를 찾아보니까 포함배제의 원리라는 듣보잡이 나왔다. 이게 말은 쉬운데 또 문제에 적용해 보니까 이해하기가 쉽지 않다.

조합만 써서 빡세게 푸는 사람도 있고 둘다 섞어서 푸는 사람도 있고 수학 문제라서 그런지 다양한 풀이가 나오는 것 같다.

 

$f(index, card, state)$

index: 몇 번째 숫자까지 왔는지 (0~index-1 번째 숫자까지 적절히 카드를 썼다는 뜻)

card: 남아 있는 카드 장수

state: 이전에 포카드가 1번 이상 나왔는지(나왔으면 1 아니면 0)

 

$f(index, card, state)=\{$

$\quad (card<0): 0$

$\quad (index=13): (state \; and \; (card=0))$ 이 참이면$1$, 아니면 $0$

$\quad (others): \sum\limits_{i=0}^4 {4 \choose i}f(index+1, card-i, state \; or \; (i=4))$

$\}$

 

그리고 처음에 카드의 수 $n$이 주어지니까

$f(0, n, 0)$ 을 구하면 된다.

 

끗