백준 13343번 Block Game

문제

You are attending the International Construction by Preschoolers Contest. Unfortunately, you are too old to participate, but you still enjoy watching the competition.

In between rounds, you are walking around the contest area when you see a toddler, one of the contestants, playing with her blocks. Annoyed that she is having all the fun, you decide to challenge her to a game.

You set up two stacks of blocks of a certain height. Then, you and the toddler take turns removing some number of blocks from the stack which contains the largest number of blocks (if both stacks have the same number of blocks, the current player can choose either stack to remove blocks from). The number of blocks removed must be a positive multiple of the number of blocks in the smaller stack. For instance, if there is a stack with 5 blocks, and one with 23 blocks, then the current player can remove 5, 10, 15 or 20 blocks from the stack of 23 blocks. The player who empties one of the stacks wins the game.

You have graciously decided to take the first move, but then a worry strikes you – might this devious preschooler still be able to beat you?

문제풀이

사용한 알고리즘 : DP

강산님의 블로그를 참고하여 풀이를 작성하였습니다.

(1) 생각

 N, M 이 주어졌을 때 다음과 같은 경우를 생각할 수 있습니다. ( N > M 으로 생각 )

    1] N 이 M 의 배수인 경우.

        -> 무조건 이길 수 있다.

    2] M < N < 2*M 인 경우.

        -> M , N-M 으로 상대에게 넘김 ( M > N-M )

    3] 2*M < N 인 경우.

        이때는 2가지 경우로 생각할 수 있습니다.

        1. M , N%M 상태로 상대에게 넘기는 경우.

        2. N%M + M , M 상태로 상대에게 넘기는 경우. 

           이 경우 상대는 2] 상태로 받았으므로 M, N%M 상태로 나에게 줄 수 밖에 없습니다.

        즉, 나는 M, N%M 상태를 상대에게 넘길 수도, 내가 갖을 수도 있습니다.

        따라서 M, N%M 상태에서 승리 할 수 있다면 내가 갖으면 되고, 

        승리할 수 없다면 상대에게 주면 됩니다.

        따라서 2*M < N 인 경우 무조건 승리할 수 있습니다.

(2) 코드 7~27

 과정(1)의 생각을 토대로 dp 를 찾는 함수를 만들어주었습니다.

 N, M이 10^18이므로 배열로 담을 수 없어 map으로 받아주었습니다.

 

	#include <bits/stdc++.h>
	using namespace std;
	typedef long long ll;
	typedef pair<ll, ll> pii;
	ll N, M;
	map<pii, bool> dp;
	bool path(ll n, ll m) {
	if (dp.count(pii(n, m))) return dp[pii(n, m)]; // 방문함
	bool ret = false;
	// n이 m으로 나누어 떨어지면 그냥 이김
	if (n % m == 0) ret = true;
	// 2*m 보다 n 이 작으면 n에서 m 빼는 수 밖에 없다.
	// 이후 상대 차례의 반대가 내 답
	else if (n < m * 2LL) ret = !path(m, n - m);
	// 2*m 보다 n 이 크면 2가지 가능
	// 1. m, n%m 의 상태로 상대에게 넘겨주기.
	// 2. n%m + m , m 의 상태로 상대에게 넘겨주기. 이경우 m, n%m 이 나에게 온다.
	// 즉 나는 m, n%m 의 상태를 상대에게 줄 수도, 내가 갖을 수도 있다.
	// m, n%m 의 상태에서 이길 수 있으면 내가 갖고, 아니면 상대한테 주면 된다.
	// 즉 나는 무조건 이길 수 있다.
	else ret = true;
	return dp[pii(n, m)] = ret;
	}
	int main() {ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
	cin >> N >> M;
	if (N < M) swap(N, M);
	if (path(N, M)) cout << "win" << '\n';
	else cout << "lose" << '\n';
	return 0;
	}

view raw BOJ 13343.cpp hosted with ❤ by GitHub