[BOJ] 9658번: 돌 게임 4

https://www.acmicpc.net/problem/9658

돌이 i개 있을 때 선수가 이기면 $D[i]=1$, 그렇지 않다면 $D[i]=0$ 이라고 합시다. 이 때

$D[0] = 1, D[1] = 0, D[2] = 1, D[3] = 0$ 임은 자명합니다. 이후의 값에 대해서는,

$D[i]$를 구하기 위해서 $D[i-1], D[i-3], D[i-4]$를 생각해야 합니다. 만약 이 셋중 어느 하나라도 값이 0이라면 돌이 $i$개일 때 선수가 이길 수 있습니다. 예를 들어 $D[i-1] = 0$인 경우, 선수가 $i$개의 돌 중 1개를 가져가면 후수는 돌이 $i-1$개인 게임의 선수와 같은 입장이고 이 때 후수는 패배하기 때문입니다. 이 성질을 바탕으로 Dynamic Programming을 하면 됩니다.

https://github.com/encrypted-def/BOJ/blob/master/9658.cpp