(C++) - LeetCode (easy) 292. Nim Game

https://leetcode.com/problems/nim-game/description/

Nim Game - LeetCode

공식을 알아내 푸는 문제였습니다.

📕 풀이방법

📔 풀이과정

2^31까지 제한을 두므로 O(n)으로도 시간초과가 납니다. 이는 brute force나 dp로 풀기 어려우며 어떤 공식을 찾아야 함을 유추할 수 있습니다.

n = 1 ~ 3인 경우 바로 그 만큼의 돌을 가져가면 되기 때문에 1이 답입니다.

n = 4인 경우 처음에 무엇을 가져가도 돌이 3이하로 남기 때문에 패배하므로 0이 답입니다.

즉, 게임 종료 직전 매번 4가 남는 경우 패배함을 알 수 있습니다.

이는 4의 배수인 경우 나와 상대편 합쳐 4개씩 가져가도록 상대방이 맞추면 내가 패배함을 의미합니다.

📔 정답 출력 | 반환

4의 배수면 0, 아니면 1을 반환합니다.

---

📕 Code

📔 C++

class Solution {
public:
    bool canWinNim(int n) {
        return n % 4;
    }
};

---

*더 나은 내용을 위한 지적, 조언은 언제나 환영합니다.