[C++] 백준 9655: 돌 게임

문제

[C++] 백준 9655: 돌 게임 SILVER 5
https://www.acmicpc.net/problem/9655

 

---

 

접근 방법

이 문제는 돌을 1개 또는 3개씩 가져갈 수 있을 때,
누가 이기는지(SK / CY) 를 판단하는 게임 문제이다.

 

처음에는 규칙을 직접 몇 개 적어보며 확인했고,
그 결과 돌의 개수가 홀수면 SK, 짝수면 CY가 이긴다는 패턴을 발견했다.
그래서 실제로는 홀짝 판단만으로도 문제를 해결할 수 있었다.

 

DP 알고리즘을 활용한 풀이2

DP(동적 계획법) 풀이로도 풀 수 있을 것 같은데,

아직 DP 구현이 어려워서 다른 사람의 블로그를 참고하여 함께 확인해보았다.

(참고 블로그: https://beginnerdeveloper-lit.tistory.com/83) 

 

DP 공부를 열심히 해보자...

 

DP 풀이에서는

• dp[i]를 i개의 돌이 남았을 때 게임이 끝나기까지의 최소 턴 수로 두고
• 한 번에 1개 또는 3개를 가져갈 수 있으므로
  dp[i] = min(dp[i-1], dp[i-3]) + 1 형태로 값을 채운다.

최종적으로 dp[n]이 홀수면 SK, 짝수면 CY가 이긴다.

 

---

 

코드

#include <iostream>
using namespace std;

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

	int n = 0;
	cin >> n;

	if (n % 2 == 0)
		cout << "CY";
	else
		cout << "SK";

	return 0;
}

 

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

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

	int n = 0;
	cin >> n;

	vector<int> dp(n + 1, 0);
	dp[0] = 0;
	dp[1] = 1;
	dp[2] = 2;

	for (int i = 3; i <= n; i++)
		dp[i] = min(dp[i - 1] + 1, dp[i - 3] + 1);

	if (dp[n] % 2 != 0)
		cout << "SK";
	else
		cout << "CY";

	return 0;
}