4342번: 유클리드 게임

문제 링크: 4342번: 유클리드 게임

개요

매 턴 큰 수에서 작은 수의 배수를 빼서 큰 수를 0으로 먼저 만드는 사람이 이기는 게임 이론 문제이다. 두 플레이어가 최적의 방법으로 게임을 하므로, 이번 턴에 만들 수 있는 상황 중 다음 턴에 그 상황에 처한 상대방이 질 수밖에 없는 경우가 하나라도 있으면 이번 턴의 플레이어가 승리한다는 개념을 이용한다. 유클리드 호제법을 응용하여 풀 수 있다.

isWin 함수

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

int isWin(int v, int u) {

	// v <= u 로 유지
	if (v > u) {
		int tmp = v; v = u, u = tmp;
	}

	// 이번 턴에서 두 수가 나누어떨어지면 이번 턴 플레이어가 승
	if (u % v == 0) return 1;

	// 이번 턴에서 큰 수에서 작은 수를 여러번 뺄 수 있으면 이번 턴 플레이어가 승
	if (u / v > 1) return 1;

	// 다음 턴에서 상대방이 지면 이번 턴 플레이어 승
	return !isWin(v, u - v);
}

isWin(v, u)는 이번 턴에 두 수가 v와 u일 때 이번 턴 플레이어가 승리하면 1, 패배하면 0을 반환한다. v<=u를 유지하도록 swap을 해주었다. v와 u에 따라 세 가지 경우로 나눠서 생각하겠다.

1. u가 v로 나누어 떨어지는 경우

이 경우엔 무조건 u를 0으로 만들 수 있으므로 이번 턴 플레이어가 승리한다.

2. u에서 v를 여러번 뺄 수 있는 경우 (u에서 v를 나눈 몫이 2 이상인 경우)

이 경우엔 이번 턴 플레이어가 만들 수 있는 경우가 두 가지 이상임을 의미한다.
이번 턴의 수가 (7, 19)인 경우를 생각해보자. 이번 턴에 만들 수 있는 경우는 (7, 12)와 (5, 7)이 있다. (7, 12)를 만들어서 다음 턴으로 넘겼을 때, 다음 턴 플레이어가 만들 수 있는 경우는 (5, 7)밖에 없고, 이는 이번 턴에서 플레이어가 만들 수 있는 경우이기도 하다. 따라서 이번 턴 플레이어는 두 가지 중 자신이 이길 수 있는 경우를 선택할 수 있는 상황이라는 결론을 얻는다. (우리는 둘 중 어느 경우가 이번 턴 플레이어를 이길 수 있게 하는지 모르지만, 둘 중 한 경우는 이번 턴 플레이어를 이길 수 있게 한다는 것은 확신할 수 있다.)
이를 일반화해보자. 이번 턴의 수가 (v, u)이고 u에서 v를 나눈 몫이 q라고 하면, 이번 턴에서 만들 수 있는 경우는 (v, u - v), (v, u - 2v), … (v, u - (q - 1)v), (v, u - qv)로 q가지가 있다. 우리가 주목할 것은 마지막 두 가지 경우 (v, u - (q - 1)v)와 (v, u - qv)이다.
마지막에서 두 번째 경우인 (v, u - (q - 1)v)는 항상 큰 수에서 작은 수를 나눈 몫이 1이다. 그러므로 이 경우를 만들어서 넘겼을 때, 다음 턴 플레이어가 만들 수 있는 경우는 (v, u - q v)로 하나밖에 없다. 이는 이번 턴 플레이어가 만들 수 있는 마지막 경우와 같다.
A경우가 이길 수 있는 경우라면 A경우의 다음 턴에서 만들어지는 유일한 경우 B경우는 질 수밖에 없는 경우임이 자명하다.
따라서 u에서 v를 나눈 몫이 2 이상인 경우, 이번 턴 플레이어는 (v, u - (q - 1)v)와 (v, u - qv)중 하나를 선택해서 무조건 승리할 수 있다.

3. u에서 v를 한 번밖에 못 빼는 경우 (u에서 v를 나눈 몫이 1인 경우)

이 경우엔 이번 턴 플레이어가 만들 수 있는 경우의 수가 한 가지이지만, 해당 경우의 승패를 알 수 없다. 따라서 재귀를 이용해 다음 턴이 승리할 수 있는 경우(1)라면 0을 반환하고, 다음 턴이 패배하는 경우(0)라면 1을 반환한다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

#include <iostream> 
#pragma warning(disable:4996)
#pragma warning(disable:6031)
using namespace std;

int isWin(int v, int u);

int main4342() {

	int a, b;
	scanf("%d %d", &a, &b);
	while (a != 0 && b != 0) {

		if (isWin(a, b)) printf("A wins\n");
		else printf("B wins\n");

		scanf("%d %d", &a, &b);
	}

	return 0;
}

int isWin(int v, int u) {

	// v <= u 로 유지
	if (v > u) {
		int tmp = v; v = u, u = tmp;
	}

	// 이번 턴에서 두 수가 나누어떨어지면 이번 턴 플레이어가 승
	if (u % v == 0) return 1;

	// 이번 턴에서 큰 수에서 작은 수를 여러번 뺄 수 있으면 이번 턴 플레이어가 승
	if (u / v > 1) return 1;

	// 다음 턴에서 상대방이 지면 이번 턴 플레이어 승
	return !isWin(v, u - v);
}