백준 9655번 돌 게임 - C++

문제

---

돌 게임은 두 명이서 즐기는 재밌는 게임이다.

 

탁자 위에 돌 N개가 있다. 상근이와 창영이는 턴을 번갈아가면서 돌을 가져가며, 돌은 1개 또는 3개 가져갈 수 있다. 마지막 돌을 가져가는 사람이 게임을 이기게 된다.

 

두 사람이 완벽하게 게임을 했을 때, 이기는 사람을 구하는 프로그램을 작성하시오. 게임은 상근이가 먼저 시작한다.

 

입력

첫째 줄에 N이 주어진다. (1 ≤ N ≤ 1000)

 

출력

상근이가 게임을 이기면 SK를, 창영이가 게임을 이기면 CY을 출력한다.

 

문제 링크

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

 

 

풀이

---

해답은 굉장히 쉽다.

홀수 번호면 상근이가 이기고, 짝수 번호면 창영이가 이긴다.

 

너무 간단하게 답이 나오는데 왜 그런지를 알아보면 이렇다.

 

돌이 1개 일때는 선공이가, 2개일 때는 후공이가 이기는게 확정이다.

현재는 선공이 상근이기 때문에 돌이 1개일 때는 상근이가, 2개일 때는 창영이가 이긴다.

 

그런데 이 이후의 돌의 개수를 우리는 이런 식으로 잘라 볼 수 있다.

 

 

3개 = 1 + 2개

 

 

이는 게임 룰 상 1개 혹은 3개를 집어야하기 때문인데, 돌의 개수에서 1 또는 3을 빼는 대신 선 후공을 바꾸는 개념으로 볼 수 있다.

이렇게 되면 우리는 3개의 돌에서 돌을 하나 뺀 후, 창영이가 선공으로 시작한 것으로 볼 수 있는 것이다.

 

이때 남은 돌은 2개인데, 돌이 2개 남을 경우 후공이 이기므로 상근이가 이기는 것이 확정된다.

 

그렇다면 이후의 게임들에 대해서는 확정된 결과를 메모이제이션 한 뒤, 다시 사용할 수 있다.

그렇기에 우리는 게임의 결과를 이렇게 볼 수 있다.

 

 

! Function 결과 (현재 돌의 개수 - 1개 혹은 3개)

 

 

이게 무슨 뜻인가... 하고 난해할 수 있는데, 결국은 현재 돌의 개수에서 1 또는 3을 뺀 돌의 개수의 결과의 반대되는 결과라는 뜻이다.

현재 돌의 개수가 4개라면, 돌이 3개일 때 혹은 돌이 1개일 때의 결과의 반대 결과가 해답이 된다.

 

그런데 짝수에서 홀수를 빼면 홀수고, 홀수에서 홀수를 빼면 짝수이기에 결국에는 짝수 결과는 홀수 결과의 반대, 홀수 결과는 짝수 결과의 반대가 되어 번갈아가며 나오게 된다. ▼

 

 

 

C++ 코드

---

#include <iostream>

using namespace std;

int N;

int main() {
    cin >> N;

    if (N % 2 == 0) 
        cout << "CY";
    else
        cout << "SK";
}