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

 

[ Contents ]

 

 

1. 문제 (링크 참조)

9656번: 돌 게임 2

 

 

 

2. 문제 풀이

 돌은 1개 혹은 3개씩 가져갈 수 있으며, 마지막 돌을 가져가는 사람이 지게 됩니다.

 두 사람이 완벽하게 게임을 진행했다고 가정하고, n이 주어졌을 때 이기는 사람을 구해야 합니다. (상근이가 먼저 시작)

 

2022.02.12 - [Algorithm] - [Algorithm] 메모해두고 불러와서 사용하는 동적 프로그래밍(DP)

[Algorithm] 메모해두고 불러와서 사용하는 동적 프로그래밍(DP)

 DP문제로 마지막에 돌이 1개 혹은 3개 남았을 경우만 판별하면 됩니다.

 

 

 

3. 코드

# 입력
n = int(input())

# DP
if n == 1:
    print('CY')
elif n == 2:
    print('SK')
elif n == 3:
    print('CY')
else:
    dp = [-1] * (n+1)
    dp[1] = 'CY'    # 창영이 이김
    dp[2] = 'SK'    # 상근이 이김
    dp[3] = 'CY'    # 창영이 이김

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

 dp[i-3]인 경우를 상정해야 하므로, 1부터 3까지는 dp값을 세팅해둡니다.

 그리고 4부터 n까지 돌을 1개씩 늘려가며 돌이 1개 혹은 3개 남은 상황일 때 누구 차례인지를 알아보고 승패를 판별합니다.

 

cf) 돌 게임 1

9655번: 돌 게임

 백준 9655 돌 게임 문제는 승리조건이 반대입니다. 마지막 돌을 가져가는 사람이 이기는 게임으로, 맨 마지막 print만 정반대로 출력하면 됩니다..

 

 (사실 좀 더 생각해보면.. 돌 게임의 승패는 홀짝으로 나누어지게 됩니다.)

 dp 테이블을 출력해보면 쉽게 알 수 있습니다.