[백준/BOJ] 백준 9658번 : 돌 게임 4

www.acmicpc.net/problem/9658

9658번: 돌 게임 4

지금 하는 사람이 -1,-3,-4 해서 하나라도 다음 상대가 지는 것이 있으면 지금 하는 사람은 승리한다

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int cache[1001];

int Solve(int n)
{
	//4이하의 값은 구해져 있다
	if (n <= 4)
		return cache[n];

	for (int i = 5; i <= n; i++)
	{
		//-1,-3,-4 해서 하나라도 다음상대가 지는것이 있으면 지금하는 사람은 승리한다
		cache[i] = (!cache[i - 1] || !cache[i - 3] || !cache[i - 4]);
	}

	return cache[n];
}

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

	int n;

	cin >> n;

	cache[1] = 0;//지금 하는 사람 패
	cache[2] = 1;//지금 하는 사람 승
	cache[3] = 0;//지금 하는 사람 패
	cache[4] = 1;//지금 하는 사람 승

	if (Solve(n) == 1)
		cout << "SK";
	else
		cout << "CY";

	return 0;
}