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

문제 출처: https://www.acmicpc.net/problem/9657

9657번: 돌 게임 3

dp[i] = 1이면 돌이 i개 일때 현재 차례인 사람이 승리

dp[i] = 0이면 돌이 i개 일때 현재 차례인 사람이 패배

 

base case

dp[1] = 1

dp[2] = 0

dp[3] = 1

dp[4] = 1

dp[i-1],dp[i-3],dp[i-4]중 하나라도 0이라면 dp[i] = 1 하나도 0이 없다면 0

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<cstring>
#include <string>

using namespace std;


int dp[1001];


int main() {
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);


    int N; cin >> N;

    dp[1] = 1; //현재 차례가 승리
    dp[2] = 0; //현재 차례가 패배
    dp[3] = 1;
    dp[4] = 1;
    for (int i = 5; i <= N; i++) {
        if (dp[i - 1] == 0)dp[i] = 1;
        if (dp[i - 3] == 0)dp[i] = 1;
        if (dp[i - 4] == 0)dp[i] = 1;
    }

 

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






}