[실버 3] 백준 9657 - 돌 게임 3 (파이썬)

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

풀이

• 돌이 N개 있을 때, SK와 CY가 번갈아 가면서 돌을 가져간다.
• 한번에 1, 3, 4개의 돌만 가져갈 수 있다.
• 마지막 돌을 가져가는 사람이 이긴다.
• SK가 먼저 시작할 때, 누가 이기는지 판단하는 문제이다.

D[i]를 i개의 돌이 있을 때 SK가 이길수 있는가를 나타내는 Boolean 배열로 설정한다.

• True → SK가 이기는 경우
• Fasle → CY가 이기는 경우

핵심은 현재 상태에서 내가 이길 수 있는 수를 선택하면 이긴다는 점이다.

즉, D[i] = not D[i - 1] or not D[i - 3] or not D[i - 4] 이다.

초기 조건은 다음과 같이 설정한다.

D[1] = True   # SK가 1개 가져가서 승
D[2] = False  # SK가 1개 가져가면 CY가 1개 가져가서 승
D[3] = True   # SK가 3개 가져가서 승
D[4] = True   # SK가 1개 => CY가 3개 (패), 혹은 SK가 4개 가져가서 바로 승

점화식은 다음과 같이 정리한다.

for i in range(5, 1001):
    D[i] = (not D[i-1]) | (not D[i-3]) | (not D[i-4])

SK의 입장에서 i - 1, i - 3, i - 4로 만들었을 때 그중 하나라도 CY의 승리라면 SK는 그 수를 선택해서 이길 수 없다.

예를 들어서 i = 5라고 가정하면,

D[5] = (not D[4]) | (not D[2]) | (not D[1])

• D[4] = True → CY가 이길 수 없음 (SK가 이길 수 있음)
• D[2] = False → CY가 이김
• D[1] = True → CY가 이길 수 없음

not D[4] = False
not D[2] = True
not D[1] = False

False or True or False → True

코드

# 백준 9657 - 돌게임 3
# 분류 : 다이나믹 프로그래밍

N = int(input())

D = [False] * 1001

D[1] = True
D[2] = False
D[3] = True
D[4] = True

for i in range(5, 1001) :
    D[i] = (not D[i - 1]) | (not D[i - 3]) | (not D[i - 4])

if D[N] :
    print("SK")
else :
    print("CY")