백준 4342 유클리드 게임 - C++

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

4342번: 유클리드 게임

다음 포스팅부터는 게임 문제 말고 다른 문제로 돌아오겠습니다..

 

 

<풀이>

 

크게 보면 간단한 문제? 

 

경우를 좀 나눠 생각하면 명쾌한 풀이가 나온다 . A > B인 A,B를 입력으로 받은 두 숫자라고 하면,

 

1. A = KB, 즉, A가 B의 배수인 경우, 해당 턴에 (A, B).를 받은 사람이 바로 승리한다. 

2. A = KB + M (M!=0) 인 경우, K가 1인 경우와 1이 아닌 경우로 나눠지는데 

   2-1 K =1인 경우, 해당 턴의 플레이어에게는 선택권이 없다. A-B를 하는 방법밖에 없다.

   2-2 반면, K > 1인 경우, 해당 턴의 플레이어는 2가지 선택지가 있는데, 

   1) 만약, (B, M)을 상대에게 넘기면 지는 경우, A - (K-1)B 를 넘겨주면 상대방은 다시 2-1 상태로 가기 때문에 승리

   2) 넘기면 이기는 경우, A - KB를 간단히 넘겨주면 승리

 

즉, K > 1이 넘는 경우에서 턴을 잡은 경우, 무조건 승리 가능하다.

 

#include <iostream>

using namespace std;
using ll = long long;

int solve(ll a, ll b, bool player) {
	// a > b

	if (a % b == 0) {
		return player;
	}

	if (a / b == 1) {
		// 현재 플레이어에게 조정 권한 X
		return solve(b, a % b, !player);
	}
	else {
		// a = kb + m이라고 했을 때,
		// (b, m)이 만약 현재 플레이어가 넘겨주면 지는 숫자 조합이면,
		// 현재 플레이어는 (k-1)만 빼고 넘겨주면 (b,m)을 받아올 수 있다.
		// 반대로 이기는 판이면, kb를 빼고 넘겨주면 상대방에게 (b, m) 강요 가능
		return player;
	}
}

int main(void) {

	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);

	ll a = 1, b = 1;
	while (1) {
		cin >> a >> b;
		if (a + b == 0) break;
		if (a < b) {
			ll tmp = a;
			a = b;
			b = tmp;
		}
		if (!solve(a, b, 0))
			cout << "A wins" << "\n";
		else
			cout << "B wins" << "\n";
	}
	return 0;
}