문제
문제설명
유클리드 게임은 두 명이서 하는 게임이고, 자연수 2개로 시작한다. 동혁이와 동규는 유클리드 게임을 하려고 한다. 동혁이가 먼저 시작한다. 동혁이는 큰 수를 작은 수의 배수만큼 뺀다. 이때, 큰 수는 음이 아닌 정수가 되어야 하며 전보다 작아져야 한다. 그런 다음 동규는 동혁이가 한 것과 똑같이 큰 수를 작은 수의 배수만큼 뺀다. 이런식으로 두 플레이어는 서로 번갈아가면서 게임을 한다. 이때, 큰 수를 0으로 만든 사람이 게임을 승리하게 된다.
예를 들어, 다음과 같이 (25, 7)로 시작한 게임을 생각해보자.
25 7
11 7
4 7
4 3
1 3
1 0
위와 같이 게임을 하게 되면, 동혁이가 이기게 된다. (큰 수와 작은 수는 각 턴에서 큰 수와 작은 수이다.)
시작하는 두 자연수가 주어졌을 때, 두 플레이어가 최적의 방법으로 게임을 할 때, 누가 이기는지 구하는 프로그램을 작성하시오.
입력
입력은 여러 줄로 이루어져 있다. 각 줄은 게임을 시작하는 두 숫자이다. 항상 동혁이가 먼저 게임을 시작한다. 두 각 입력에 대해서 동혁이가 이기면 A wins를, 동규가 이기면 B wins를 출력한다.자연수는 231-1보다 작거나 같다. 입력의 마지막 줄에는 0 두 개가 주어진다.
출력
각 입력에 대해서 동혁이가 이기면 A wins를, 동규가 이기면 B wins를 출력한다.
해결방법
우선 작은 수의 배수를 큰 수에서 빼는 방식으로 진행해가며 먼저 0이되는 사람이 이기는 게임이다.
처음에는 큰 수를 최대한 작은 값으로 나누는 것이라고 생각했었는데 이러한 방법이 모든경우 적용되는 것이 아니였고 열심히 생각해 보았는데 모르겠어서 다른 풀이를 찾아보고 참고하여 풀어보았다.
우선 게임을 진행하며 얻을 수 있는 경우를 세가지로 나누었다.
1. 작은 수를 빼서 0을 만들 수 있을때
이 경우에는 0을 만들면 된다.
-
a<2b일때
이 경우에는 다른 방법이 없이 a-b를 하고 순서를 넘겨 주어야 한다. -
a>2b일때
이 경우에는 넘겨줄 값이 선택가능하다.
결국 3번째 경우에서 본인에게 유리한 것을 판단하는 방법을 찾는것이 제일 큰 문제였다.
일단 1의 경우일때 현재차례가 게임을 이기기에 승자를 반환하도록 해주었고 2또한 a=a%b로 순서를 넘기도록 해주었다.
3번째의 경우에는 a의 값을 a%b, a%b+b 중 하나를 선택하게 해주었다.
어떤식으로 구현을 해야될지 모르겠어서 재귀를 이용하여 a%b를 건네주었을때 내가 이기는 경우가 나오면 a%b를 선택하고 아닌경우에는 a%b+b를 넘겨주도록 작성을 해봤는데 성공했다.
if (game(a % b, b) == 1) a = a % b;
else a = b + a % b;코드
#include<iostream>
using namespace std;
void set_ab(int* a, int* b)
{
if (*a < *b)
{
int tmp = *a;
*a = *b;
*b = tmp;
}
}
int game(int a, int b)
{
set_ab(&a, &b);
int k = 0;
while (1)
{
if (a % b == 0) return k % 2;
else if(a/b ==1)
{
a = a - b;
set_ab(&a, &b);
k++;
}
else {
if (game(a % b, b) == 1) a = a % b;
else a = b + a % b;
set_ab(&a, &b);
k++;
}
}
}
int main() {
int a, b;
cin >> a >> b;
while (a || b )
{
if (game(a, b) == 0) cout << "A wins\n";
else cout << "B wins\n";
cin >> a >> b;
}
}
후기
어려운문제였고 최적의 방법으로 게임을 한다는 부분의 구현이 어려웠다.
그리고 3번째 방법을 구현할때 vs에서 테스트를 해보다가 모르겠다 이거 되려나? 하고 작성했던 코드가 성공된거라 아직도 왜 된것지 잘모르겠다. 게임이론이 거의다 이런 문제던데 좀더 해봐야 할것 같다.
