9657: 돌 게임3

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

9657번: 돌 게임 3

설명

핵심 아이디어

기존의 돌 게임 문제와 유사하다. 차이점이 있다면 가져갈 수 있는 돌의 개수가 1개, 3개에서 추가로 4개단위도 가져갈 수 있게 됐다.

• 다이나믹 프로그래밍: 작은 문제부터 풀어보자
• dp[1] ~ dp[4] 에 대해서 배열에 저장해 놓고 푼다.
• 상근이부터 시작할 때 돌이 1개, 3개, 4개 있을 때는 무조건 상근이가 승리한다. 하지만 돌이 2개 있을 때는 상근이가 1개 밖에 가져갈 수 없기 때문에 창영이가 승리한다.
• 돌이 5개 이상일 때는 한번에 게임이 끝나지 않기 때문에 상근이가 1개 3개 4개를 가져갔을 때 남은 돌의 개수에 따라 승리하는 사람을 구해보면 된다.

조건을 이해하기가 어려웠기 때문이다. 문제를 분석해보자면, 이 게임은 SK의 입장에서 풀이해야 한다. 모든 참가자가 자신이 이길 수밖에 없는 구조로 게임을 하는데, 선공이 상근이이기 때문에 문제의 주도권은 SK이 가지고 있다. 즉, n개의 돌이 있을 때, n - 1과 n - 3, 그리고 n - 4에 누가 그 돌을 가져가는지를 알면 누가 이길 지 알 수 있다. SK는 무조건 자기가 이기는 수로 게임을 한다. 즉, n - 1, n - 3, n - 4의 돌을 가진 사람이 한 명이라도 CY이라면 SK는 그 수를 통해서 자신을 승리로 이끌 것이다. 하지만 세 경우 모두 SK이 갖고 있다면 CY도 마찬가지로 자기가 이길 수밖에 없는 경우로만 게임을 하기 때문에 CY의 승리가 된다.

 

정리하면, n - 1, n - 3, n - 4가 모두 SK라면 n은 CY의 승리 / n - 1, n - 3, n - 4에 하나라도 CY가 있다면 SK의 승리이다.

코드 구현

import sys
input = sys.stdin.readline

n = int(input())

dp = ["", "SK","CY","SK","SK"]

for i in range(5, n+1):
	if dp[i-1] == "CY" or dp[i-3] == "CY" or dp[i-4] == "CY":
		dp.append("SK")
	else:
		dp.append("CY")
print(dp[n])

문제를 풀 때 이해가 잘 가지 않아서 어려웠던 문제다...