백준 9658번 돌 게임 4 C++

출처 : https://www.acmicpc.net/problem/9658

 

완벽하게 게임을 했을 때 : 최선의 선택을 했을 때라고 이해하고 문제를 풀었다.

상근이의 기준에서

동전이 1개일 때 : 1개 가져가면 패배

동전이 2개일 때 : 1개 가져가면 상대방이 1개 가져가서 승리

동전이 3개일 때 : 1->1->1 패배, 3개 가져가도 패배

동전이 4개일 때 : 3개 가져가면 상대방이 1개 가져가서 승리

5개부터는 dp를 이용하여 해결할 수 있다.

동전이 5개 이상인 n 개라면 3가지로 나눠볼 수 있다.

처음 4개를 가져갔다면 n-4개일 때,

처음 3개를 가져갔다면 n-3개일 때,

처음 1개를 가져갔다면 n-1개일 때이다. 이 각각의 경우는 처음에 상근이가 가져가고 창영이의 턴으로 넘어갔기 때문에

동전이 n-k개 있을때(k = 4, 3, 1)의 승패의 반대가 된다.(상근이 기준) 그러므로 세 경우 모두 승리였다면 모두 패배가 되므로 승리할 가능성이 없어지고, 패배가 하나라도 있다면 그 경우를 고르면 승리이기 때문에

세 경우 모두 승리이면 패배, 아니면 승리이다.

 

코드에서는 상근이를 기준으로 0은 패배, 1은 승리이다.

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>

using namespace std;
typedef long long ll;

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

	int n;
	cin >> n;
	int dp[1001] = { 0 };

	dp[1] = 0;
	dp[2] = 1;
	dp[3] = 0;
	dp[4] = 1;
	for (int i = 5; i <= n; i++) {
		int sum = dp[i - 4] + dp[i - 3] + dp[i - 1];
		if (sum == 3) {
			dp[i] = 0;
		}
		else {
			dp[i] = 1;
		}
	}
	if (dp[n] == 0) {
		cout << "CY";
	}
	else {
		cout << "SK";
	}
};