백준 9657 - 돌 게임 3

문제 설명

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

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

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

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

---

 

 

 

 

 

 

제한 사항

---

 

 

 

 

 

 

풀이

문제를 요약하면, N개의 돌을 두 명이 번갈아가며 1, 3, 4개씩 가져갈 수 있을 때 누가 이길지 구하는 것이다.

 

이 문제는 베스킨 라빈스와 비슷한 게임이라고 생각할 수 있다.

즉, 일종의 님게임이다.

항상 상근이가 먼저 시작하기 때문에 상근이의 시점으로 게임을 풀어나가면 된다.

우선, 게임의 상태를 정의해 보자.

문제의 조건에 의해 돌이 0개 남을 수 없으니 1부터 생각해 보자.

돌이 1개 남아 있다면 상근이는 무조건 이길 수 있다.

1개를 가져가면 된다.

마찬가지로 3, 4개도 동일한 논리가 적용된다.

반대로 돌이 2개 남으면 상근이는 무조건 질 수밖에 없다.

돌을 2개 가져갈 수 없어 1개를 가져가면 창영이가 무조건 이기기 때문이다.

이를 표로 정리해 보면 다음과 같다.

1	2	3	4	5	6
승리	패배	승리	승리	?	?

5와 6을 채울 수 있게 되면 문제를 푼 것과 동일하다.

5를 채우는 경우를 생각해 보자.

돌이 5개가 남은 채로 상근이가 돌을 가져가는 차례라고 한다면 상근이는 1, 3, 4개를 가져갈 수 있다.

이때, 상근이가 가져가고 남은 돌은 4, 2, 1개가 된다.

1, 4개를 가져가게 되면 다음 차례에 창영이가 무조건 이기는 상태가 된다.

하지만, 3개를 가져가게 되면 2개가 남아 상근이는 무조건 이기는 상태로 만들 수 있다.

즉, 돌을 가져갔을 때 상대가 무조건 지게 만들 수 있다면 그 상태는 승리 상태가 된다.

---

 

 

 

 

 

전체 코드

#include <bits/stdc++.h>
using namespace std;

int N;
vector<bool> states;
vector<int> dx = { 1, 3, 4 };

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

	cin >> N;
	states.resize(N + 1, false);

	states[0] = false;
	states[1] = true;
	states[2] = false;
	states[3] = true;
	states[4] = true;

	for (int i = 5; i <= N; i++)
	{
		for (int j = 0; j < 3; j++)
		{
			//패배 상태로 만들 수 있으면 승리상태
			int prev = i - dx[j];
			if (!states[prev]) states[i] = true;
		}
	}

	if (states[N]) cout << "SK";
	else cout << "CY";

	return 0;
}

---