문제 설명.
게임 이론에 속한 문제. 두 명의 player가 있어서 두 개의 수가 주어졌을 때 차례대로 큰 수에서 작은 수를 자연수배만큼 곱해서 빼다가(이때 뺀 값은 음이 아닌 정수.), 마지막에 0을 만드는 유저가 승리하는 게임이 진행된다.
좀 더 구체적인 예시로 들어가보자. 두 명의 플레이어A, B가 있다. 모든 게임은 항상 A부터 시작한다. 각 라인마다 두 수 a, b (설명에서는a>=b라 가정한다.)가 주어진다. 이 때 두 플레이어는 모두 이기기 위한 최선의 선택을 한다.(게임은 항상 진행된다.)
문제에 나와있는 a, b = 34, 12라는 예시를 생각해보자. 이경우 A는 두 가지 선택을 할 수 있다.
1. a-b : 이 때 다음 수는 22, 12가 된다.
2. a-2b : 이 때 다음 수는 12, 10이 된다.
이 경우 2번째 케이스를 살펴보자.
B의 차례에서 B가 할 수 있는 선택지는 a-b로 유일하며 그 결과는
a,b == 10,2로 나오게 된다.
그리고 마지막으로 A가 a-5b를 하고, 0을 만들게 됨으로써 게임은 끝이 나고, A가 승리하게 된다.(결과적으로 A의 첫 번째 2번의 선택은 최선의 선택이다.)
풀이.
위의 설명으로부터 우리는 경우의 수를 a, b에 따라 3가지 방법으로 나눌 수 있다.
각각의 방법들.
1. (case1) a%b == 0 인 경우.
이 경우 당연히 해당 턴의 플레이어가 이기게 되는 케이스이다.
2. (case2) a < 2*b 인 경우.
이 경우 해당 턴의 플레이어는 게임을 진행하는 선택지가 하나밖에 없다.
즉, 해당 턴의 플레이어가 게임에서 진행하는 행동은 a-b로 강제된다.
3. (case3) a > 2*b 인 경우.
이 경우 해당 턴의 플레이어는 여러 선택지를 얻을 수 있다.
a < n*b라고 할 때 총 n-1개의 선택지가 존재한다.
풀이 설명.
결과적으로 이 게임은 게임이 1, 2번 케이스만으로 진행되는, 선택지가 항상 강제된 것이 아니라면 게임을 진행했을 때 처음으로 case3을 마주치는 플레이어가 이길 수 밖에 없는 구조로 이루어져 있다. 그 이유는 각 케이스마다 항상 특정 수 쌍들이 나올 수 밖에 없다는 것 -맨 위의 34, 12를 생각해보자. A가 1번 선택지를 골랐을 때 그 다음 결과는 필연적으로 12, 10이 되고, 이는 A가 2번 선택지를 골랐을 때와 같은 결과이다.
조금 더 자세한 설명을 위해 이를 일반화해보자. 여기서는 가독성을 위해 좀 더 간단한 기호를 사용할 필요가 있다.
- case1 :
(1), - case2 :
(2), - case3 : 2 이상의 임의의 자연수 n에 대해
n*b < a < (n+1)*b를 만족한다고 했을 때[n].(당연히[1] == (2)가 되지만 구분을 위해 따로 썼다.)
이 경우 숫자들은 ...(2)(2)[n_1](2)(2) ... [n_2]... [n_k](2)... (1)로 나타낼 수 있게 된다. 이 때 A가 첫 번째 [n], 즉, [n_1]을 만났다고 가정하자. A는 게임을 이기기 위한 최선을 선택을 할 것이고,
- 가정1. 계산을 통해
[n_1]을B가 마무리짓게 되면 스스로가 이길 것이란 것을 안다. 그 결과A는a-(n-1)*b를 시행하고, 이후B의 경우[n_1]이(2)로 바뀌기 때문에B가[n_1]을 마무리짓게 된다. - 가정2. 계산을 통해 스스로가
[n_1]을 마무리짓게 되면 게임을 이기게 되는 경우 단순히A는a-n*b를 해주면 된다.
좀 더 자세한 이해를 돕기 위한 팁.
2가지 참고사항. (직접 해보길 권장한다.)
- 위의 설명이 그대로가 잘 이해가 안되는 경우
[n]이 1가지만 있는 케이스를 직접 써보면 좋을 것이다. - 일반적인 케이스에서
[n_{k+1}]에 접촉하는 선택지는[n_k]에 먼저 접촉하는 사람이 결정할 수 있다.
풀이 코드.
from sys import stdin
def gcd(a,b):
if a%b == 0:
return True
elif a-b<b:
return False if gcd(b,a-b) else True
else:
return True
while True:
a,b = map(int,stdin.readline().strip().split())
if a == 0:
break
elif a<b:
a,b = b,a
if gcd(a,b):
print('A wins')
else:
print('B wins')cf.
-
풀이와는 직접 연관이 없기에 종료시점을 따로 빼서 쓰자면
a,b ==0,0으로input이 들어갈 때 실행이 종료가 된다고 설명되어 있다. -
게임이론에 속한 내용을 쓸까 고민하다가 너무 길게 쓰는 것 같아 그만둔다. 위키피디아의 내용을 참고하면 좋을 것 같아 공유해본다. 이 게임의 경우 실재 보상이 어떤 다른 것이 없이 '이긴다' 라는 것 하나밖에 없고, 이외의 제약조건같은 것이 없어 좀 나누기가 애매하다.(그나마 순차적 게임이라는 것 정도?..) 그러나 '이긴다'는 것 자체가 이 게임의 보상이 된다라고 하면, 비협조적 전개형 게임이라고 말할 수 있을 것 같다.
