백준 9655번 바로가기

나의 풀이

game = [-1] * 1001

game[1] = 1 #SK win
game[2] = 0 #CY win
game[3] = 1 #SK win

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

print("SK" if game[n]==1 else "CY")

CODE REVIEW

  1. 베스킨라빈스31류의 돌게임! 다만 1개 또는 3개의 돌을 꺼낼 수 있다. 그리고 마지막 돌을 꺼낸 사람이 이긴다.
  2. 점화식을 생각하면 편리하다! $a_n$번째 승자는 $a_{n-1}$번째와 $a_{n-3}$번쨰 승자와 동일하다. 따라서 game[i-1]과 game[i-3]을 확인해서 누가 이겼는지를 업데이트해주면 된다.
  3. 규칙성을 이용할 수도 있는데, 계속해서 구해나가다보면 N이 홀수면 ‘SK’ 짝수면 ‘CY’가 이기는 것을 확인할 수 있다.
    • 다만 여기서는 DP이용하기 위해서 위 같은 논리를 이용했다.