[백준 9656번] [동적 계획법] 돌 게임 2

Approach

https://viyoung.tistory.com/295 문제와 완벽히 동일하다.

[백준 9655번] [동적 계획법] 돌 게임

 

다만, 마지막에 돌을 둔 사람이 지는 것이므로 승자만 바꿔주면 된다.

Code

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)

using namespace std;

int dp[1001];
int n;

int dp_value(int x)
{
    if (x < 1)
        return 987654321;
    if (dp[x] != -1)
        return dp[x];
    else
    {
        return dp[x] = min(dp_value(x - 1), dp_value(x - 3)) + 1;
    }
}

int main(void)
{
    memset(dp, -1, sizeof(dp));
    dp[1] = 1;
    dp[3] = 1;
    cin >> n;

    int check = dp_value(n);
    if (check % 2 == 1)
    {
        cout << "CY\n";
    }
    else
    {
        cout << "SK\n";
    }
    return 0;
}