[ 백준 / C++ ] 9657 : 돌 게임 3

[ 문제 ]

 

9657번: 돌 게임 3 (acmicpc.net)

 

[ 접근방법 ]

 

현재 돌이 n개 있다고 했을 때, 1개나 3개나 4개를 가져가면 n-1개 혹은 n-3개 혹은 n-4개가 남게 된다.

 

n-1개 혹은 n-3개 혹은 n-4개를 상대에게 넘겨주었을 때 승패 여부를 알 수 있다면

현재 상태에서의 승패 여부도 알 수 있다.

 

위 아이디어를 DP를 통해 구현해준다.

 

[ 소스코드 ]

 

#include <iostream>

using namespace std;

int n;
bool dt[1010] = {false, true, false, true, true};

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;

    for (int i = 5; i <= n; i++)
    {
        if (!dt[i - 1] || !dt[i - 3] || !dt[i - 4])
            dt[i] = true;
        else
            dt[i] = false;
    }

    if (dt[n])
        cout << "SK";
    else
        cout << "CY";

    return 0;
}