[백준] 9657번 돌 게임 3 (silver 3

#include <iostream>
#include <cmath>
#include <cstdlib>
using namespace std;

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

	int n;
	cin >> n;

	int dp[1001];
	dp[1] = 1;
	dp[2] = 0;
	dp[3] = 1;
	dp[4] = 1;

	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] == 1) {
		cout << "SK" << "\n";
	}
	else {
		cout << "CY" << "\n";
	}
	

	
}

//dp를 활용한 풀이 차피 인당 1,3,4개를 가져가는 경우밖에 없고 이는 
//5이상의 경우를 1,1,3 1,3,1 1,4등등 숫자의 배열을 어떻게 할 지의 문제.
//두명은 각각 자신의 최대이익이 되는 선택을 하게되고 이는 한마디로, 각 부분들이 최적이라는 얘기
//따라서 dp를 이용해 최소부터 구하는 범위까지 차근차근 구하면 답을 구할 수 있음