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

https://www.acmicpc.net/problem/9657

9657번: 돌 게임 3

문제

---

돌 게임은 두 명이서 즐기는 재밌는 게임이다.

탁자 위에 돌 N개가 있다. 상근이와 창영이는 턴을 번갈아가면서 돌을 가져가며, 돌은 1개, 3개 또는 4개 가져갈 수 있다. 마지막 돌을 가져가는 사람이 게임을 이기게 된다.

두 사람이 완벽하게 게임을 했을 때, 이기는 사람을 구하는 프로그램을 작성하시오. 게임은 상근이가 먼저 시작한다.

 

입력

---

첫째 줄에 N이 주어진다. (1 ≤ N ≤ 1000)

 

출력

---

상근이가 게임을 이기면 SK를, 창영이가 게임을 이기면 CY을 출력한다.

 

문제 풀이

---

dp 문제.

돌이 1개, 3개, 4개 일 때는 상근이가 이기고, 2개 일 때에는 창영이가 이긴다.

두 사람이 완벽하게 게임을 하므로 상근이는 창영이가 이기도록 하는 경우를 차단하려 할 것이다. 따라서 돌이 i개 있을 때, 1턴 이전에 존재하는 i-1개, i-3개, i-4개의 경우에서 창영이가 이기는 경우가 하나라도 있다면 1턴 뒤는 상근이가 이기게 되므로, 상근이는 해당 경우로 유도할 것이다.  반면 1턴 이전의 i-1개, i-3개, i-4개의 경우에서 모두 상근이가 이기는 경우라면, 1턴 뒤는 무조건 창영이가 이기게 된다.

 

아래는 코드.

#include <iostream>
using namespace std;

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

	int N;
	cin >> N;
	string* dp = new string[1001];
	dp[0] = "";
	dp[1] = "SK";
	dp[2] = "CY";
	dp[3] = "SK";
	dp[4] = "SK";
	for (int i = 5; i < 1001; i++)
	{
		if (dp[i - 1] == "SK" && dp[i - 3] == "SK" && dp[i - 4] == "SK")
		{
			dp[i] = "CY";
		}
		else
		{
			dp[i] = "SK";
		}
	}
	cout << dp[N] << "\n";
	return 0;
}