[Python] 백준 9655 돌 게임 - 동적 계획법 (DP)

백준 홈페이지 문제와 개인적인 풀이를 작성한 글 입니다.

 

백준문제 - 9655 : 돌 게임

9655번: 돌 게임

 

---

 

문제

 

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

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

두 사람이 완벽하게 게임을 했을 때, 이기는 사람을 구하는 프로그램을 작성하시오.

게임은 상근이가 먼저 시작한다.

 

입력

 

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

 

출력

 

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

 

예제 입력 1	예제 출력 1
5	SK

 

코드 - 구현?

 

# n 개 입력받기 
n = int(input())

if n % 2 == 0:
  print("CY")
else:
  print("SK")

 

이런 간단한 문제를 왜 썼으며, DP 라고 적어놓았을까?

 

동적 계획법 (DP) 는 아직 이론을 정리하지 않았습니다.

가장 기본적이고 간단하게 볼 수 있는 문제라고 판단되어 작성하게 되었습니다

실제로 백준 구분에서도 DP 로 구분하는 분들이 굉장히 많습니다. ( 시리즈로 문제가 있습니다. )

동적계획법 에 대한 내용은 다음 글에서 다루도록 하겠습니다. 

 

코드 - 동적 계획법 (DP)

 

import sys
input = sys.stdin.readline

N = int(input())

# DP 의 기초 세팅 값은 다음과 같이 처리한다.
dp = [-1] * 1001

# 0은 스킵 1번 SK
dp[1] = 1

# 2번 CY
dp[2] = 0

# 3번 SK
dp[3] = 1

for i in range(4, N + 1):
    if dp[i-1] or dp[i-3]:
        dp[i] = 0
    else:
        dp[i] = 1

if dp[N] == 0:
  print("CY")
else:
  print("SK")