[백준🥈5] #9655 돌 게임 (python)

https://www.acmicpc.net/problem/9655

9655번: 돌 게임

 

문제

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

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

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

입력

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

출력

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

예제 입력 1

5

예제 출력 1

SK

 

✔️ Code

import sys
input = sys.stdin.readline

n = int(input())

dp = [-1] * 1001

dp[1] = 1 # SK
dp[2] = 0 # CY
dp[3] = 1 # SK

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

if dp[n] == 1:
    print("SK")

else:
    print("CY")

 

✏️ Comment

N = 1 상근 승

N = 2 창영 승

N = 3 상근 승

N = 4 창영 승

N = 5 상근 승

이런 식으로 순차대로 경우를 따져보면 홀수일 때는 상근이가, 짝수일 때는 창영이가 게임에서 이긴다는 것을 알 수 있다. 홀수, 짝수, 홀수, 짝수가 번갈아 나오므로 만약에 어떤 n에서 1이나 3을 뺐을 때 상근이가 이기는 경우라면 해당 n은 창영이가 이기는 경우일 것이므로 dp[n] = 0 이 되도록 했다.

참고하면 좋을 것 같은 풀이 공유한다..

https://velog.io/@miiingirok/%EB%B0%B1%EC%A4%80-9655.-%EB%8F%8C%EA%B2%8C%EC%9E%841-Python

[백준] #9655. 돌게임1 (Python)