[Baekjoon] DP - 9658 돌 게임 4 (오답노트)

문제

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

 

풀이

d[n]: 돌의 수가 n 개인 경우 우승자

상근이가 먼저 시작하기 때문에 "한 번"이라도 창영이가 마지막 돌을 가져가게 된다면 상근이의 승리

 

예시

d[1] = 1 (상근 마지막돌, 창영 승)

d[2] = 1 1 (창영 마지막돌, 상근 승)

d[3] = 1 1 1 (상근 마지막돌, 창영 승)

            3      (상근 마지막돌, 창영 승)

d[4] = 1 3 (창영 마지막돌, 상근 승)

           3 1  (창영 마지막돌, 상근 승)

           4     (상근 마지막돌, 창영 승)

 

코드

import sys

n = int(sys.stdin.readline().rstrip())
d = [False] * (n + 5)

# False: 창영이 우승, True: 상근이 우승
d[1] = False
d[2] = True
d[3] = False
d[4] = True

for i in range(5, n + 1):
    # 마지막 돌을 상근이만 가져갈 수 있으면 
    if d[i - 1] and d[i - 3] and d[i - 4]:
        d[i] = False # 창영이 승
    else:
        d[i] = True

print("SK" if d[n] else "CY")