[백준] 9657 돌 게임 3 with Python

📌 BOJ 9657 돌 게임 3

💡 조건

1. 탁자 위에 돌 N개가 있다. 상근이와 창영이는 턴을 번갈아가면서 돌을 가져가며, 돌은 1개, 3개 또는 4개 가져갈 수 있다.
2. 마지막 돌을 가져가는 사람이 게임을 이기게 된다.
3. 두 사람이 완벽하게 게임을 했을 때, 이기는 사람을 구하는 문제.
4. 게임은 상근이가 먼저 시작한다.
5. 첫째 줄에 N이 주어진다. (1 ≤ N ≤ 1000)
   상근이가 게임을 이기면 SK를, 창영이가 게임을 이기면 CY을 출력한다.
6. 다이나믹 프로그래밍 유형의 문제

🔖 예제 및 실행결과

예제 1

6

실행결과 1

SK

⌨️ 문제 풀이

1. 상근이를 기준으로 DP 배열을 구성할 것이다. 그렇다면, 어떻게하면 상근이가 이길 수 있을지에 대해서 생각해보면 좋다.
   "완벽하게 게임을 한다" 라는 구절을 통해서 어떻게든 상근이가 이길 방법이 있다면,
   DP 배열에서 그 개수는 상근이가 이기는 판으로 기록을 해두는것이 옳다.

2. 문제에서 돌을 네개까지 가져 갈 수 있으니 dp[4]까지 직접 계산하며 살펴보자.
   돌이 1개일 때, 상근이는 1개를 가져갈 수 있으며 이기게 된다. -> 1
   돌이 2개일 때, 상근이는 1개를 가져갈 수 있으며 지게 된다. -> 0
   돌이 3개일 때, 상근이는 1, 3개를 가져갈 수 있으며, 두 경우 모두 이길수 있다. -> 1
   돌이 4개일 때, 상근이는 1, 3, 4개를 가져갈 수 있으며, 4개를 가져가면 이길 수 있다. -> 1

3. (2)번과 같이 계산했을 때, DP 리스트는 아래와 같이 구성된다.
   0 ~ 4까지 계산한 결과 + 입력받은 n - 4개의 0으로 초기화한 리스트

dp = [0, 1, 0, 1, 1] + [0] * (n - 4)

4. dp[가져갈 돌의 개수]로 보면 1 혹은 0의 값이 있다.
   1의 값일 때를 살펴보면 상근이가 먼저 시작을 했을 때 이길 수 있고, 그게 아니라면 진다.
   반대로 0의 값일 때는 무조건 이길 수 있다.

5. (4)번에서 알아본 것을 토대로 보면, 돌 한개, 세개, 네개 가져갔을 때의 dp값에 0이 있다면 무조건 상근이가 이긴다는 것이다.

6. 반복문을 통해서 n번 째 리스트까지 계산하여 값을 정한 뒤, dp[n] 을 출력하면 된다.

🖥 소스 코드

from sys import stdin

n = int(stdin.readline())
arr = [0, 1, 0, 1, 1] + [0] * (n - 4)

for i in range(5, n + 1):
    if 0 in [arr[i - 1], arr[i - 4], arr[i - 3]]:
        arr[i] = 1
    else:
        arr[i] = 0

print('SK' if arr[n] else 'CY')