[BAEKJOON] 9655 돌 게임 (C++)

가볍게 풀어보고 다른 거 하려다가 생각보다 고민을 많이 했다.

문제링크

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

9655번: 돌 게임

문제

돌을 1개 또는 3개 가져갈 수 있을 때 N번째 돌을 가져가는 사람이 누구인지 출력하는 문제

 

풀이

경우의 수 자체만 생각해보면 2^N 으로 매우 많다. 하지만 두 사람이 완벽하게 게임을 했다는 조건이 주어진다.

N번째 돌에 대해서 생각해보면, N-1번째, N-3번째 돌을 가져간 사람은 승자가 될 수 없다.

그 돌을 가져간 사람의 다음 차례 사람이 완벽하게 게임을 한다면, 각각 1개나 3개를 가져가 N번째 돌을 가져갈 것이기 때문이다.

 

다이나믹 프로그래밍을 통해 k번째 돌을 누가 가져갈지 생각할 때, k-1번째와 k-3번째 돌을 누가가져갔는지 알 수 있다면 그 다음 차례 사람이 돌을 가져갈 것임을 알 수 있다.

 

초기 dp[1], dp[3] 을 1로 초기화한다. (1 -> SK가 돌을 가져간 상황)

dp배열을 돌며 i번째 돌을 누가 가져갔는지 확인 후 i+1, i+3번째 dp값을 업데이트 한다. 

이때 이미 dp값이 업데이트 되어있다면 업데이트 하면 안된다. 이미 더 빠르게 해당 순서의 돌을 가져간 경우가 존재하기 때문이다.

 

코드 

#include <bits/stdc++.h>

#define endl "\n"

typedef long long ll;
using namespace std;

int N;
int dp[1010];

void Solve() {
	cin >> N;
	dp[1] = dp[3] = 1;
	for (int i = 1; i <= N; i++) {
		if (dp[i] == 0) continue;

		if (dp[i] == 1) {
			if (dp[i + 1] == 0) dp[i + 1] = 2;
			if (dp[i + 3] == 0) dp[i + 3] = 2;
		}
		else if (dp[i] == 2) {
			if (dp[i + 1] == 0) dp[i + 1] = 1;
			if (dp[i + 3] == 0) dp[i + 3] = 1;
		}
	}
	if (dp[N] == 1) cout << "SK";
	else cout << "CY";
}

int main() {
	ios::sync_with_stdio(false); cin.tie(NULL);
	//freopen("input.txt", "r", stdin);
	Solve();
	return 0;
}