[Python - Dynamic Programming] 9657 돌 게임 3

📌 문제

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

 

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

 

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

📌 입력

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

📌 출력

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

📌 문제 풀이

👨‍🏫 접근

문제가 꽤 어려웠다. 조건을 이해하기가 어려웠기 때문이다. 문제를 분석해보자면, 이 게임은 SK의 입장에서 풀이해야 한다.

 

모든 참가자가 자신이 이길 수밖에 없는 구조로 게임을 하는데, 선공이 상근이이기 때문에 문제의 주도권은 SK이 가지고 있다.

 

즉, n개의 돌이 있을 때, n - 1과 n - 3, 그리고 n - 4에 누가 그 돌을 가져가는지를 알면 누가 이길 지 알 수 있다. SK는 무조건 자기가 이기는 수로 게임을 한다. 즉, n - 1, n - 3, n - 4의 돌을 가진 사람이 한 명이라도 CY이라면 SK는 그 수를 통해서 자신을 승리로 이끌 것이다. 하지만 세 경우 모두 SK이 갖고 있다면 CY도 마찬가지로 자기가 이길 수밖에 없는 경우로만 게임을 하기 때문에 CY의 승리가 된다.

 

정리하면, n - 1, n - 3, n - 4가 모두 SK라면 n은 CY의 승리 / n - 1, n - 3, n - 4에 하나라도 CY가 있다면 SK의 승리이다.

👨‍🏫 문제 풀이

📄 전체 코드

n = int(input())

tmp = ["SK", "CY"]
d = [-1] * 1001

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

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

print(tmp[d[n]])

 i - 4까지 참고하기 때문에 

📄 준비

n = int(input())

tmp = ["SK", "CY"]
d = [-1] * 1001

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

i - 4까지 참조할 예정이므로 d[4] 까지는 미리 값을 넣어둔다.

📄 풀이

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

print(tmp[d[n]])

위의 경우를 토대로 반복을 한다.

📌 총평

뭔가 어이없었던 문제. 게다가 점수도 실버라서 뭔가 아쉬웠다.