[BOJ 13343 // C++] Block Game

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 13343번 문제인 Block Game이다.
문제는 아래 링크를 확인하자.

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

13343번: Block Game

 

이번 턴에 건드려야 하는 block stack의 block 개수를 $A$, 다른 block stack의 block 개수를 $B$라 하자. $A$가 $B$의 배수이면 이번 턴에 block을 조작하는 사람이 이김은 자명하다. 만약 $A>2B$가 성립한다면 이번 턴에 block을 조작하는 사람은 다음으로 조작하게 될(즉, 이번 턴에 조작해야 하는 block stack이 아닌 다른) block stack을 자신이 처음으로 조작할지 상대가 먼저 조작하게 할지 마음대로 결정할 수 있다. 위와 같은 경우들은 이번 턴에 조작하는 사람이 항상 이기게 된다.

 

위의 경우를 제외하면 남는 경우는 $B<A<2B$인 경우인데, 이 때 가능한 유일한 행동은 현재의 block stack에서 $B$개의 block을 제거하고 턴을 넘기는 것임을 관찰하자. 이 경우 승패는 다음 턴에 따라 결정된다.

 

위 과정은 여러 번 반복될 수 있으나, 반복할 때마다 $A$의 크기는 절반 미만으로 줄어들어 반복 횟수가 $O(lg(A)+lg(B))$밖에 안 되므로 이와 같은 과정을 시뮬레이션하는 것으로 문제를 충분히 해결할 수 있다.

 

아래는 제출한 소스코드이다.

#include <iostream>
#include <utility>
using namespace std;
typedef long long ll;

ll A, B;
int ans;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> A >> B;
	if (A < B) swap(A, B);
	while (B < A && A < B * 2) {
		ans ^= 1;
		A -= B;
		swap(A, B);
	}

	if (ans) cout << "lose";
	else cout << "win";
}