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

 

[ Contents ]

 

 

1. 문제 (링크 참조)

9657번: 돌 게임 3

 

 

2. 문제 풀이

 각 플레이어는 번갈아가며 돌을 1개, 3개 또는 4개를 가져갈 수 있으며, 마지막 돌을 가져가는 사람이 게임을 이깁니다. n개가 주어졌을 때 이길 사람을 출력해야 합니다. (플레이어: 상근, 창영 / 시작은 상근이부터) 

 

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

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

 돌 게임 시리즈 문제입니다. 앞선 문제와 달리 4개를 한 번에 가져갈 수 있습니다.

 

 

3. 코드

# 입력
n = int(input())

# DP
if n == 1:
    print('SK')
elif n == 2:
    print('CY')
elif n == 3:
    print('SK')
elif n == 4:
    print('SK')
else:
    dp = [-1] * (n+1)
    dp[1] = 'SK'    # 상근이 이김
    dp[2] = 'CY'    # 창영이 이김
    dp[3] = 'SK'    # 상근이 이김
    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])

 문제 푸는 방법은 크게 달라지지 않습니다.

 돌이 1개 혹은 3개, 4개 남는 상황을 DP로 구하고 승자를 판별합니다.\