[BOJ 17080 // C++] 결함 게임

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 17080번 문제인 결함 게임이다.
문제는 아래 링크를 확인하자.

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

17080번: 결함 게임

게임이론 문제이다.

 

적은 개수의 돌의 경우를 먼저 살펴보면 다음과 같다:

돌이 1개 있다면 탑이 하나밖에 만들어질 수 없으므로 선공의 승리이다.

돌이 2개 있다면 선공이 2인 돌을 먼저 골라 탑을 1개로 유도할 수 있으므로 선공의 승리이다.

돌이 3개 있다면 선공이 무엇을 골라도 후공이 탑을 2개로 유도할 수 있다.

(선공이 1을 고른다면 후공이 3을 골라 탑 2개로 유도할 수 있고, 선공이 2 또는 3을 고른다면 후공이 1을 골라 탑 2개로 유도할 수 있다.)

돌이 4개 있다면 선공이 2를 고른 후 후공이 (강제로) 1을 고르면 선공이 3을 고르는 것으로 탑 3개를 만들어 승리할 수 있다.

 

이를 일반화해보자.

1) 돌이 짝수개이면 선공의 승리이다. 전략은 다음과 같다:

돌이 두개 남기 전까지 선공은 두번째로 작은 돌만을 계속 골라 새로운 돌탑의 바닥으로 한다. 후공은 남은 가장 작은 돌을 그 위에 올리는 행동밖에 할 수 없다.

마지막 남은 돌 2개로 탑 1개 또는 2개를 만드는 것을 강요하여 선공이 승리를 차지한다.

 

2) 돌이 4n+1개 꼴이면 선공의 승리이다. 전략은 다음과 같다:

돌 1개 남을 때까지 두번째로 작은 돌만을 계속 골라 새로운 바닥의 돌탑으로 하면 짝수개의 돌탑이 만들어진다. 남은 하나의 돌을 새로 배치하여 홀수개의 돌탑을 만든다.

 

3) 돌이 4n+3개 꼴이면 후공의 승리이다. 전략은 다음과 같다:

Case 1) 선공이 첫 번째 돌을 집어간 경우:

남아있는 돌은 짝수개이다. 돌이 2개 남을 때까지 두번째로 작은 돌만을 계속 골라 새로운 바닥의 돌탑으로 하자. 이 때, 만들어진 돌탑의 개수에 따라 남은 돌중 작은 돌을 선택할지 큰 돌을 선택할지 결정한다.

Case 2) 선공이 첫 번째 돌이 아닌 돌을 집어간 경우:

후공은 첫번째 돌을 가져간다. 다음 선공의 행동을 기다린다.

Case 2-0) 돌이 하나 남은 경우:

선공은 남은 돌을 배치한다. 이것으로 짝수개의 돌탑이 완성되었으므로 후공의 승리이다.

Case 2-1) 선공이 첫 번째 돌을 집어간 경우:

"Case 1"의 과정을 반복한다.

Case 2-2) 선공이 첫 번째 돌이 아닌 돌을 집어간 경우:

후공은 첫번째 돌을 가져간다. 이제, 처음으로 돌아간다.

 

따라서, 위의 내용을 구현하는 것으로 문제를 해결할 수 있다.

 

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;

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

	int N; cin >> N;
	if (N % 4 == 3) cout << 2;
	else cout << 1;
}