백준 - 돌 게임4(9658)

Dynamic Programming

문제

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

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

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

입력

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

출력

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

---

def solution(n):
    dp = [0] * (n + 5)
    dp[1] = 0
    dp[2] = 1
    dp[3] = 0
    dp[4] = 1
    # 편의상 dp의 1은 상영이, 0은 창근이가 이긴다는 의미로 할당
    
    for i in range(5, n + 1):
        if dp[i - 1] and dp[i - 3] and dp[i - 4]:
            dp[i] = 0
        else:
            dp[i] = 1
            
    if dp[n] == 1: 
        print('SK')
    else:
        print('CY')


n = int(input())
solution(n)

상영이 먼저 돌 4개(n = 4) 조건으로
돌 1개 => 창근, 돌 2개 => 상영, 돌 3개 => 창근, 돌 4개 => 상영으로 승부가 결정되고
그 이후 나머지 결과는 이에 기반해 1, 3, 4개를 베팅하는 3가지의 경우에서 상영이가 1가지라도 이길 수 있으면 시작우선권에 의해 결과를 가져올 수 있다('SK' 출력). 하지만 3가지의 모두 빼도 박도 못하게 창근이가 이기게 되면 'CY'를 출력