[백준 python] 9658번 돌 게임 4 - 동적프로그래밍(DP)

[백준 python] 9658번 돌 게임 4 - 동적프로그래밍

레벨: 실버2

언어: python

---

문제풀러가기

9658번: 돌 게임 4

📑풀이 과정

DP를 이용해서 풀이할 수 있는 문제이다.

나는 이 문제를 풀기 위해 돌이 N개 있을 때

후공자의 승패 여부를 dp 배열에 저장하고 사용하였다.

 

dp[N]이 True 면 선공자의 승이면서 후공자의 패이다.

 

아래의 표와 같이 후공이 지고 이기는 상황을 알 수 있다.

 

이때 돌이 N개 일때 누가 이기는 알기 위해서
N - 1 일때
N - 3 일때
N - 4 일때
후공자가 승인지 패인지를 보면 현재 게임에서 누가 이기는지 알 수 있다.

상근이가 돌을 가져가는 갔을 때 후공자 창영이가 승하면 상근이는 패하고
후공자 창영이가 패하면 상근이가 승한다.

 

돌 수	1	2	3	4	5	6
후공자 승 패	승	패	승	패	패	패

 

📋풀이 코드

N = int(input())

dp = [False]* 1001
dp[2] = True

for i in range(4, N+1):
  if not dp[i-1]:
    dp[i] = True
  if not dp[i-3]:
    dp[i] = True
  if not dp[i-4]:
    dp[i] = True

print('SK' if dp[N] else 'CY')

if not dp[i-1]

돌 N개에서 한개를 가져온 값이 False면 후공자가 패 한 것이고 현재 게임에서는 선공자가 이기게 된다.

나머지 밑에 if문도 같은 맥락이다.

다른 풀이

다른 풀이를 찾아보니깐 7개 마다 패승 규칙이 반복된다고 한다.
반복되는 규칙을 찾아서 코드를 작성해도 풀 수 있다.

---