[ 백준 / C++ ] 9656 : 돌 게임 2

[ 문제 ]

 

9656번: 돌 게임 2 (acmicpc.net)

 

[ 접근방법 ]

 

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

 

n-1개 혹은 n-3개를 상대에게 넘겨주었을 때 승패 여부를 알 수 있다면 현재 상태에서의 승패 여부도 알 수 있다.

 

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

 

[ 소스코드 ]

 

#include <iostream>

using namespace std;

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

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

    cin >> n;

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

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

    return 0;
}