[백준/Python] 9657번: 돌 게임 3

문제

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

9657번: 돌 게임 3

---

문제 요약

탁자 위에 N개의 돌이 있을 때, 상근이와 창영이는 턴을 번갈아가면서 돌을 가져간다.

 

마지막 돌을 가져가는 사람이 승리한다.

 

돌은 1개, 3개, 4개를 가져갈 수 있다.

 

두 사람이 완벽하게 게임을 했을 때, 이기는 사람을 출력한다.

---

코드

N = int(input())

dp = [0] * 1001
# dp[i]: i개의 돌이 주어졌을 때, 0이면 패배, 1이면 승리 (i개의 돌로 시작)

dp[1] = 1
dp[2] = 0
dp[3] = 1
dp[4] = 1

for i in range(5, 1001):
    if dp[i-1] == 0: # i-1개의 돌이 남았을 떼 상대가 이긴다면 그 다음 턴에 1개를 가져가면 승리
        dp[i] = 1
    if dp[i-3] == 0: # i-3개의 돌이 남았을 떼 상대가 이긴다면 그 다음 턴에 3개를 가져가면 승리
        dp[i] = 1
    if dp[i-4] == 0: # i-4개의 돌이 남았을 떼 상대가 이긴다면 그 다음 턴에 4개를 가져가면 승리
        dp[i] = 1

if dp[N] == 1:
    print("SK")
else:
    print("CY")

---

코드 설명

상근이 차례에서 i개의 돌이 남았을 때 승리했다면, 창영이도 승리한다.

 

예를 들어, 돌이 6개가 주어졌을 때, 상근이가 1개의 돌을 가져가면, 창영이가 5개의 돌로 시작하는 경우와 같다. 이 때 상근이가 이전에 5개의 돌이 주어졌을 때 승리했기 때문에 창영이도 승리한다.

 

즉 자신이 먼저 가져갈 수 있어서 승리했던 게임은 상대가 먼저 가져갈 수 있다면 똑같이 승리한다.

 

+ 상대가 이긴다는 것은 다음은 자신의 턴이다.