예제: Nim Game
문제
You are playing the following Nim Game with your friend: There is a heap of stones on the table, each time one of you take turns to remove 1 to 3 stones. The one who removes the last stone will be the winner. You will take the first turn to remove the stones.Both of you are very clever and have optimal strategies for the game. Write a function to determine whether you can win the game given the number of stones in the heap.
Example:
Input: 4 Output: false Explanation: If there are 4 stones in the heap, then you will never win the game; No matter 1, 2, or 3 stones you remove, the last stone will always be removed by your friend.
풀이
Nim 게임을 하는데, 승리 가능성 여부를 return하는 문제이다.
문제를 설명하자면, 플레이어는 자기 턴마다 3이하의 숫자를 취할 수 있다.
주어진 숫자에서 턴을 돌아가며 3 이하의 숫자를 빼다가, 마지막으로 수를 0으로 만드는 플레이어가 승리하는 게임이란다.
처음에 필자는 재귀함수를 사용하여 문제를 풀려고 했다.
어차피 제출하면 time exceeded가 나는 코드이므로, 간단히만 설명하겠다.
1. 내 턴일 경우는 승리가능성이 하나라도 있다면, true를 리턴한다(OR조건).
2. 상대방 턴에서는 모두 패배할 경우만 true를 리턴한다(AND 조건).
하지만 위에 언급한대로 time exceeded가 나기 때문에, 무언가 간단한 조건이 있을 것이라고 생각했다.
결론은, n % 4 = 0 일 경우 나의 패배이다. 그 말인 즉, 내 턴에 4의 배수를 가지게 된다면 내가 무슨 경우를 택하더라도 패배한다는 이야기이다. 왜일까? 조건을 거꾸로 따라 올라가면 알 수 있다.
내 턴에 4를 가질 경우 무조건 패배한다. 상대방이 3, 2, 1 중 하나의 수를 가지기 때문이다.
그 전의 케이스가 있다고 한다면, 상대방이 7, 6, 5 중 하나의 수를 가지면 상대방이 무조건 이긴다. 3, 2, 1 숫자를 취한 후 나에게 4를 넘기면 되기 때문이다.
또 그 전의 케이스가 있다고 한다면, 내가 8을 가지고 있다면 상대방에게 7, 6, 5 중 하나의 수를 넘겨야 하므로 무조건 패배이다.
이런식으로 거꾸로 타고 올라가 보면, 결국 내가 4의 배수를 가지고 있는 경우 무조건 패배하게 된다.
전체적인 소스코드는 아래와 같다.
소스 코드
/* CASE1 */
class Solution {
public:
bool canWinNim(int n) {
return solve(0, n); //0: 내턴, 1: 상대방턴
}
bool solve(int turn, int n) {
if (turn == 1 && n <= 3) {
return false;
}
if (turn == 0 && n <= 3) {
return true;
}
int res = turn;
for (int i = 1; i <= 3; i++) {
if (turn == 0) {
res |= solve(1, n - i);
}
else {
res &= solve(0, n - i);
}
}
return res;
}
};
/* CASE2 */
class Solution {
public:
bool canWinNim(int n) {
return (n % 4);
}
};풀이 후기
두 개의 케이스를 보면 알겠지만, 구현한 코드의 라인 수도 엄청나게 차이나고, 속도도 엄청나게 차이난다. 개발자에게 있어서, 개인의 역량 차이로 인해 업무 진행률이 100배 이상 차이날 수 있다고 한다. 이런 알고리즘 문제를 풀다 보면 무슨 말인지 알 것 같기도 하다.
