[백준/BOJ] 백준 13343번 : Block Game

www.acmicpc.net/problem/13343

13343번: Block Game

높이가 n, m(n>=m)인 블록 스택이 있을 때 현재 순서에 빈 블록 스택이 있다면 현재 사람이 패배하고, n > 2 * m일때는 n에서 m을 뺄 수도 있고. 2m을 뺄 수도 있으므로 무조건 이기는 경우가 있으므로 현재 사람이 승리한다. (지금 단계에서 m을 빼고 다음 단계에서 또 m을 뺀 것과, 지금 단계에서 2m을 뺀 블록 상황은 같은 블록 상황이 된다)

 

코드

#include <iostream>
#include <algorithm>
using namespace std;

//높이가 n,m(n>=m)인 블록스택이 있을때 현재 순서가 이길 수 있는지 확인
int Solve(long long n, long long m)
{
	if (m == 0) //현재 순서에 빈 블록스택이 있다면 현재사람 패배
		return 0; //패배

	if (n > 2 * m) //n에서 m을 뺄 수도 있고, 2m을 뺄 수도 있으므로 이기는 경우가 무조건 있다 (지금단계에서 m을 빼고 다음 단계에서 또 m을 뺀것과, 지금단계에서 2m을 뺀 블록 상황은 같은 블록 상황이 된다)
		return 1; //승리

	return !Solve(max(m, n%m), min(m, n%m)); //다음 사람의 결과와 반대 결과
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	long long n, m;

	cin >> n >> m;

	if (Solve(max(n, m), min(n, m)))
		cout << "win";
	else
		cout << "lose";

	return 0;
}