[백준 c++] 9655 돌 게임

문제

https://www.acmicpc.net/problem/9655
N개의 돌이 있다.
상근이와 창영이가 턴을 번갈아가면서 돌을 가져간다.
맨 마지막에 돌을 가져가는 사람이 이긴다.
한 턴에 1개 또는 3개를 가져갈 수 있다.
상근이부터 시작한다.

풀이

DP를 이용해서 풀어보려 바등댔지만 허무하게도 짝홀 구분하는 문제였다..ㅜ

dp[i]가 1이면 i번째 턴에 돌을 가져간 것이고, dp[i]가 0이면 창영이가 돌을 가져간 것이다.

dp[i-1] 또는 dp[i-3]이 0이면 상근이가 돌을 가져가지 않은 것이므로 dp[i]에서 상근이가 돌을 가져갈 수 있다.

코드

#include <iostream>
using namespace std;
int n, dp[1001];
int main()
{
    cin >> n;
    dp[1] = 1;
    dp[2] = 0;
    dp[3] = 1;
    for (int i = 4; i <= n; i++)
    {
        if ((dp[i - 1] || dp[i - 3]) == 0)
            dp[i] = 1;
    }
    if (dp[n])
        cout << "SK\n";
    else
        cout << "CY\n";
}