백준 python 기록
백준 python 9657 돌 게임 3
작지
2021. 7. 13. 20:52
백준 링크:https://www.acmicpc.net/problem/9657
9657번: 돌 게임 3
상근이가 게임을 이기면 SK를, 창영이가 게임을 이기면 CY을 출력한다.
www.acmicpc.net

완벽하게 게임을 하라니 그걸 어케 내가 정하는거지? 라고 생각했었다.
하지만 이 게임 선공이 매우 유리하다!

5부터는 SK가 2를 만들 수 있는가 없는가에 따라 게임이 결정된다.
따라서

이런식으로 결정된다. 7 이후부터는 8이 7을 만들수 있는가 없는가에 따라 만들면된다.
풀이코드:
n=int(input())
dp=[1,1,0,1,1]
for i in range(5,n+1):
if dp[i-1] == 0 or dp[i-3] == 0 or dp[i-4] == 0:
dp.append(1)
else:
dp.append(0)
if dp[n] == 0:
print('CY')
else:
print('SK')