[BOJ] 9657번_돌 게임 3_DP (C++)

[문제]

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

상근이와 창영이는 턴을 번갈아가면서 돌을 가져간다. 돌을 가져갈 땐 한 번에 1개, 3개, 4개를 가져갈 수 있으며 마지막에 돌을 가져가는 사람이 이긴다. 두 사람이 실수없이 완벽하게 게임을 진행했을 때, 마지막에 돌을 가져가는 사람을 구하는 문제이다.

[사용 알고리즘]

DP(다이나믹 프로그래밍)

[풀이 핵심]

• dp[5]를 생각해보면 누가 이기는지 쉽게 알 수 있다. dp[5]가 상근이의 차례라고 생각했을 때, dp[5-1], dp[5-3], dp[5-4]는 창영이의 차례이다. 이 때 창영이가 1 or 3 or 4개의 돌을 가져가서 승리할 수 있으면, 무조건 상근이의 승리가 된다. 따라서 "dp[i-1] == 0 || dp[i-3] == 0 || dp[i-4] == 0" 을 만족하면 상근이가 이기고 그외에는 창영이가 이긴다.
  ->현재 턴에서 1,3,4개의 돌을 제외한 이전 턴에서 상대가 승리할 수 있으면 현재 턴에선 내가 승리한다는 개념이다.

[코드]

//boj9657번_돌 게임 3_DP

#include<iostream>

using namespace std;

int dp[1001];

int main() {
	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 - 3] == 0 || dp[i - 4] == 0) {
			dp[i] = 1;
		}
		else {
			dp[i] = 0;
		}
	}

	if (dp[N] == 1) {
		cout << "SK";
	}
	else {
		cout << "CY";
	}

	return 0;
}