[백준 9657번] 돌 게임 3 (C++)

문제링크 : https://www.acmicpc.net/problem/9657

9657번: 돌 게임 3

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MAX 987654321
#define pii pair <int, int>

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int N;
    int dp[1001];

    dp[1] = dp[3] = dp[4] = 1;  //상근이 가져감
    dp[2] = 0;

    cin >> N;

    for(int i=5; i<=N; i++)
    {
        if(dp[i-1] == 1 && dp[i-3] == 1 && dp[i-4] == 1)
        {
            dp[i] = 0;  //창영이 가져감
        }
        else
        {
            dp[i] = 1;  //상근이 가져감
        }
    }

    if(dp[N])
    {
        cout << "SK";
    }
    else
    {
        cout << "CY";
    }

    return 0;
}

돌을 1, 3, 4개를 가져갈 수 있고 처음에 상근이 가져가는 것으로 시작했기에 dp[1] = dp[2] = dp[3] = 1로 초기화한다.

(1 -> 상근이 가져간 경우 / 0 -> 창영이 가져간 경우)

 

가져갈 수 있는 경우의 수가 1, 3, 4 총 3가지이고 이 3가지에 대해 검토를 해서 한 번이라도 창영이 가져간 경우가 있더라면 다음은 상근이 가져간다. 

완벽하게 게임을 한다고 가정했으므로 상근이 마지막으로 가져갈 수 있는 경우의 수가 한 번이라도 있으면 상근이 이긴 것이다.