(Python) 백준 9655 스톤게임 – 다이나믹 프로그래밍 (DP)

by

백준이 홈페이지의 문제점과 개인적인 해결방안에 대한 글입니다.

백준 문제 – 9655 : 스톤 게임

문제 9655: 스톤 게임

'추천 관련글,

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

www.acmicpc.net

질문

둘이서 하기 좋은 게임입니다.

테이블 위에 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")