[동적계획법/DP] 백준 9658 돌 게임 4 - 파이썬(Python)

 

[ Contents ]

 

 

1. 문제 (링크 참조)

9658번: 돌 게임 4

 

 

2. 문제 풀이

 어쩌다 보니 돌 게임 시리즈... 켠왕을 하고 있네요..

 

2023.07.03 - [Algorithm] - [동적계획법/DP] 백준 9657 돌게임 3 - 파이썬(Python)

[동적계획법/DP] 백준 9657 돌게임 3 - 파이썬(Python)

 이전 문제와 달리, 마지막 돌을 가져가면 지는 걸로 바꾸면 됩니다.

 

 

 

3. 코드

# 입력
n = int(input())

# DP
if n == 1:
    print('CY')
elif n == 2:
    print('SK')
elif n == 3:
    print('CY')
elif n == 4:
    print('SK')
else:
    dp = [-1] * (n+1)
    dp[1] = 'CY'
    dp[2] = 'SK'
    dp[3] = 'CY'
    dp[4] = 'SK'

    for i in range(5, n+1):
        # 돌이 1개 혹은 3개, 4개 남은 상황일 때
        if dp[i-1] == 'CY' or dp[i-3] == 'CY' or dp[i-4] == 'CY':
            dp[i] = 'SK'
        else:
            dp[i] = 'CY'
    print(dp[n])