백준 4342: 유클리드 게임

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

4342번: 유클리드 게임

 
골드2 게임이론 문제 치고는 발상이 좀 쉬운 편이다.
 
내 차례에 숫자가
X X
2*X X
3*X X
등등등 큰 수가 작은 수의 배수라면 무조건 내가 이긴다.
 
그럼 큰 수가 작은 수의 배수가 아닌 경우라면?
큰 수를 big, 작은 수를 sma라고 부르자.
 
big=sma+1이면 (sma>1)
내 차례에 내가 할 수 있는  건 딱 한가지다. 
그리고 상대 차례에 
sma 1 이렇게 두 숫자가 주어질 거다.
그러면 상대가 이긴다.
 
big=sma+2라면 (sma>2)
내 차례에 내가 할 수 있는건 딱 한가지다.
그리고 상대 차례에
sma 2 이렇게 두 숫자가 주어질 거다.
이러면 sma 2가 이기는 경우라면 내가 지고 sma 2가 지는 경우라면 내가 이긴다.
 
big=sma+q라면 (sma>q)
내 차례에 내가 할 수 있는건 딱 한가지다.
그리고 상대 차례에
sma q 이렇게 두 숫자가 주어질 거다.
이러면 sma q가 이기는 경우라면 내가 지고 sma q가 지는 경우라면 내가 이긴다.
 
내 차례에
big=n*sma+q (n은 2 이상 자연수, n=big/sma, q=big%sma)
이라면 나는 내 차례에 무조건 이긴다.
 
만약
sma q가 지는 경우라면 나는 내 차례에 n*sma을 큰 수에서 빼는 일을 하면 sma q를 만들 수 있으니 이긴다.
sma q가 이기는 경우라면 sma+q sma는 지는 경우다. 그럼 나는 내 차례에 큰 수에서 (n-1)*sma를 빼는 일을 하면 상대 차례에 sma+q sma가 되니까 내가 이긴다.
 
그러니까 이 문제는 재귀함수로 풀 수 있다.
 
bool winner(int a, int b)라는 함수를 가정해보자.
a, b중 큰 값이 big이고 작은 값이 sma이다.
 
big>=sma*2는 이기는 경우이다. 따라서 true를 반환한다.
big이 sma의 배수면 이기는 경우이다. 따라서 true를 반환한다.
아니라면 big=sma+q인 q에 대해 winner(sma, q)의 반대, 즉 !winner(sma, q)를 반환한다. 
 
c언어로 구현하면 다음과 같다.
중간에 주석으로 오버플로우 주의라고 적어둔 부분이 있다.
big>=sma*2인지를 판단할 때 sma*2가 int 범위를 넘어설 수 있다.
그렇기 때문에 long long자료형을 쓰던가, 아니면 big/sma>=2처럼 조건식을 쓰면 된다.

int max(int n, int m)
{
	return (n > m) ? n : m;
}

int min(int n, int m)
{
	return (n < m) ? n : m;
}

bool winner(int a, int b)
{
	int big = max(a, b);
	int sma = min(a, b);

	if (big % sma == 0)
		return true;
	if (big / sma >= 2)//오버플로우 주의
		return true;
	
	return !winner(sma, big - sma);

}

int main()
{
	int a = 1, b = 2;
	while (1)
	{
		scanf("%d %d", &a, &b);
		if (a * b == 0)
			break;
		printf(winner(a, b) ? "A wins\n" : "B wins\n");
	}
}