[BOJ] 백준 4342번 : 유클리드 게임 (JAVA)

문제

유클리드 게임은 두 명이서 하는 게임이고, 자연수 2개로 시작한다. 동혁이와 동규는 유클리드 게임을 하려고 한다. 동혁이가 먼저 시작한다. 동혁이는 큰 수를 작은 수의 배수만큼 뺀다.

 

이때, 큰 수는 음이 아닌 정수가 되어야 한다.  그런 다음 동규는 동혁이가 한 것과 똑같이 큰 수를 작은 수의 배수만큼 뺀다. 이런식으로 두 플레이어는 서로 번갈아가면서 게임을 한다. 이때, 큰 수를 0으로 만든 사람이 게임을 승리하게 된다.

 

예를 들어, 다음과 같이 (25, 7)로 시작한 게임을 생각해보자.

 

 

• 25 7
• 11 7
• 4 7
• 4 3
• 1 3
• 1 0

 

 

위와 같이 게임을 하게 되면, 동혁이가 이기게 된다. (큰 수와 작은 수는 각 턴에서 큰 수와 작은 수이다.)

 

시작하는 두 자연수가 주어졌을 때, 두 플레이어가 최적의 방법으로 게임을 할 때, 누가 이기는지 구하는 프로그램을 작성하시오.

 

 

입력

입력은 여러 줄로 이루어져 있다. 각 줄은 게임을 시작하는 두 숫자이다. 항상 동혁이가 먼저 게임을 시작한다. 두 자연수는 231-1보다 작거나 같다. 입력의 마지막 줄에는 0 두 개가 주어진다.

 

 

출력

각 입력에 대해서 동혁이가 이기면 A wins를, 동규가 이기면 B wins를 출력한다.

 

 

풀이

유클리드 호제법을 응용한 게임 이론 문제였습니다.

 

 

이 게임은 두 자연수가 주어지고, 큰 수를 작은 수의 배수로 뺴면서 두 수 중 하나를 0으로 만드는 사람이 이기는 규칙입니다.

 

따라서, 기본적으로 유클리드 호제법을 이용해야하는데, 꼭 큰 수에서 작은 수의 최대 배수로 뺄 필요는 없기 때문에 어떤 경우에 선공이 이기고, 어떤 경우에 후공이 이기는지 판단해야했습니다.

 

 

먼저, 두 수가 a, b이고, a < b 관계를 만족한다고 합시다.

그렇다면, 이 수로 나올 수 있는 경우는 총 3가지가 있습니다.

 

 

(1) b % a == 0

이 경우, 선공이 b를 0으로 만들 수 있기 때문에 선공이 이깁니다.

 

 

(2) (b - a) < a

직관적으로 설명드리면, "4 7"과 같이 큰 차이가 나지 않는 수를 말합니다.

그리고 이 경우에는 선공과 후공 중 누가 이기는지 판단할 수가 없습니다.

이것은 아래 예시를 통해 누가 이기는지 판단할 수 없음을 알려주는 반례입니다.

 

 

4 7 -> 3 4 -> 1 3 -> 0 1 : 선공승

15 24 -> 9 15 -> 6 9 -> 3 6 -> 0 3 : 후공승

 

 

따라서, 2번째 케이스에서는 단순히 2번째 케이스 밖에 반복할 수 없으므로 다음 상황이 패배하면, 이번 상황은 승리한다는 식으로 누가 이기는지 알아낼 수 있습니다.

 

 

하지만, 2번째 케이스만 반복된다는 것은 아직 증명되지 않았습니다. 일단, 2번째 케이스가 반복된다는 사실이 증명됐다고 가정하고 3번째 케이스를 보겠습니다.

 

 

(3) (b - a) > a

등호를 붙이지 않은 이유는, b - a = a일 경우, 2a = b가 되어 1번째 케이스와 동일하기 때문입니다.

 

일단, 위의 과정은 정답부터 이야기하면 무조건 선공이 이깁니다.

왜 그럴까요? 예시를 통해 설명해 드리겠습니다.

 

 

만약, 두 수가 7과 25라면 2번째 케이스로 만들 수 있는 경우는 2가지가 있습니다.

"7 11"과 "4 7"이죠.

 

여기서, 두 수의 형태를 2번째 케이스로 만들어 주는 이유는, 2번째 케이스는 2번 케이스만 반복되기 때문에 별다른 변수없이 턴이 몇 번 흘렀는지에 따라 승패가 결정나게 됩니다.

 

 

선공이 "7 11"로 만들었다면, "7 11" -> "4 7" -> "3 4" -> "1 3" -> "0 1" 을 통해 선공이 이기게 됩니다.

 

반대로, 선공이 "4 7"로 만들었다면, "4 7" -> "3 4" -> "1 3" -> "0 1" 을 통해 후공이 이기게 됩니다.

 

 

여기서, 중요한 사실을 알 수 있습니다.

3번째 케이스에서는 2번째 케이스로 만들 수 있는 경우가 A, B 경우가 있는데, B는 A에서 파생되었다는 것입니다!

 

즉, 3번째 케이스에서 선공은 둘 중에 자기가 이기는 경우가 반드시 존재하고, 그 경우를 선택함으로써 필승할 수 있게 됩니다.

 

 

이제, 우리는 1번째 케이스와 3번 케이스는 선공이 이긴다는 것을 알 수 있고, 2번째 케이스는 누가 이길지 알 수는 없으나 단순히 2번 케이스만 반복되므로 누가 이기는지 판단하기 쉽다는 것을 알 수 있었습니다.

 

 

마지막으로, 2번째 케이스는 왜 3번째 케이스로는 진행되지 않고, 2번째 케이스로만 반복되는지 증명해 보겠습니다.

 

똑같이, a, b가 있고 이 둘은 a < b 관계를 만족하고, (b - a) < a를 만족한다고 합시다.

그렇다면, 한 번 유클리드 게임을 수행하면 (a, b) 에서 (b - a, a)로 변할 것입니다.

 

이제, 우리는 다음 과정도 2번째 케이스인지 확인하기 위하여  a - (b - a) < a가 성립하는지 증명해야합니다.

 

이것을 정리하면, a < b가 되고 이 조건식은 위에서 정한 base에 해당하므로 결과적으로 2번째 케이스는 항상 2번째 케이스만 반복된다는 사실을 알 수 있습니다.

 

 

유클리드 호제법과 위 과정을 이용하여 소스코드를 작성해 보시길 바랍니다.

 

 

소스코드

 

지적 혹은 조언 환영합니다! 언제든지 댓글로 남겨주세요.