[백준/9657] 돌 게임 3 (Python)

Problem : https://www.acmicpc.net/problem/9657

9657번: 돌 게임 3

 

Difficulty : Silver 3

 

Status : Solved

 

Time : 00:13:57

 

---

 

문제 설명

 

 

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

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

두 사람이 완벽하게 게임을 했을 때, 이기는 사람을 구하는 프로그램을 작성하시오. 게임은 상근이가 먼저 시작한다.

 

 

입력 및 출력

 

입력

 

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

 

출력

 

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

 

입력 예시

 

6

 

출력 예시

 

SK

 

 

---

 

풀이

 

다이나믹 프로그래밍 문제. (with 게임이론) 앞서 '똑같이' 풀이한 문제가 있으니 설명은 링크로 갈음하도록 한다. 이번에는 좀 더 깔끔하게 코드를 짤 수 있었던 것 같다.

 

2023.04.08 - [알고리즘 문제/백준] - [백준/9655] 돌 게임 (Python)

[백준/9655] 돌 게임 (Python)

 

 

풀이 코드

import sys
sys.setrecursionlimit(100000)

N = int(input())
left_list = [1, 3, 4]
dp = [-1]*(N+1)
dp[0] = True
def dfs(left) :
  if not left :
    return False
  if dp[left] != -1 :
    return dp[left]
    
  result = True
  for _left in left_list :
    if left - _left < 0 :
      continue
    result &= dfs(left - _left)

  dp[left] = not result
  return dp[left]

print("SK" if dfs(N) else "CY")

풀이 완료!