유클리드 게임( BOJ 4342 )

문제 : https://www.acmicpc.net/problem/4342

4342번: 유클리드 게임

 

문제 파악하기

주어진 두 개의 자연수를 사용하여 유클리드 게임을 했을 때, 선공을 하는 사람(동혁)이 이기는지 후공을 하는 사람(동규)이 이기는지 확인하는 문제입니다. 두 사람은 항상 최적의 방법으로 게임을 한다는 설명을 통해 우리는 시작부터 승자와 패자가 결정되었다는 걸 확인할 수 있습니다. 그럼 두 개의 숫자를 가지고 누가 이기는지 어떻게 알 수 있을까요? 이는 유클리드 게임을 분석하면 어렵지 않게 감을 잡을 수 있습니다.

 

유클리드 게임은 한 턴에 두 개의 숫자 중 큰 수(A)를 작은 수(B)의 배수로 뺍니다. 그리고 큰 숫자를 0으로 만드는 사람이 이기는 게임으로, 이 과정은 사실 유클리드 호제법의 과정에 거의 흡사합니다. 여기서 우리가 주목해야 할 점은 A와 B의 관계입니다. 유클리드 호제법과 달리 우리는 A와 B의 관계에 따라 다음 턴에 상대방의 행동을 강제할 수 있습니다. 이 점을 활용하여 문제를 해결해보겠습니다.

 

문제 해결하기

유클리드 게임 안에서 A와 B 사이의 관계는 크게 3가지로 분류할 수 있으며, 각각 게임이 종료되는 경우, 행동이 강제되는 경우, 상대방의 행동을 강제할 수 있는 경우를 의미합니다. 이 관계는 B의 값이 바뀔 때마다 갱신되며, (A, B)의 다음 상태는 항상 (B, A%B)가 됩니다.

 

(1) 게임이 종료되는 경우

- 조건식 : A%B == 0

- A가 B의 배수인 경우, 게임이 종료되며 현재 선공인 사람이 게임을 승리하게 됩니다.

 

(2) 행동이 강제되는 경우

- 조건식 : A < B*2

- 현재 선공인 사람의 행동이 (B, A-B)로 강제되는 경우입니다. 이 경우에는 이어질 상태에 따라 선공인 사람의 승패가 결정됩니다.

 

(3) 상대방의 행동을 강제할 수 있는 경우

- 조건식 : A >= B*2

- 현재 선공인 사람이 다음 상태의 선공/후공을 선택할 수 있는 경우입니다. 이 경우에는 다음 상태들을 참고해 선공/후공을 고를 수 있기에 항상 승리할 수 있습니다.

 

3가지 상태에 따라 현재 선공인 사람의 승패가 결정되며, 우리는 유클리드 호제법을 활용하여 구한 각각의 상태에 대한 승패를 구할 수 있습니다. 이 과정을 맨 마지막부터 재귀적으로 호출하면 문제를 해결할 수 있습니다.

 

소스코드

#include <stdio.h>
typedef long long INT;
 
INT a, b, ret;
 
int sv(INT a, INT b) {
    if(a < b) return sv(b, a);
 
    if(a%b == 0) return 1;
    else {
        int f = sv(b, a%b);
 
        if(a < b*2) return 1-f;
        else return 1;
    }
}
 
int main() {
    while(1) {
        scanf("%lld %lld", &a, &b);
        if(!a and !b) break;
 
        ret = sv(a, b);
 
        if(ret) printf("A wins\n");
        else printf("B wins\n");
    }
}
/*
21 17 -- 0
17 4 -- 1
4 1 -- 1
 
 
197 30 -- 1
30 17 -- 1
17 13 -- 0
13 4 -- 1
4 1 -- 1
*/

후기

유클리드 호제법과 게임 이론을 결합한 문제입니다. 문제 자체는 어렵지 않지만 알고리즘을 재귀적으로 설계하는 과정이 살짝 헷갈릴 수 있던 문제입니다. 각각의 상태에 대한 승패를 어렵지 않게 구할 수 있기에 게임 이론을 공부하는 사람에게 추천하고 싶은 문제입니다.