https://www.acmicpc.net/problem/9658
9658번: 돌 게임 4
상근이가 게임을 이기면 SK를, 창영이가 게임을 이기면 CY을 출력한다.
www.acmicpc.net
이 문제에 앞서 반드시 이전 포스팅(돌 게임 3)을 참조 부탁드린다.
이전 문제(돌 게임 3)에서처럼 이번에도 같은 로직을 적용할 수 있다.
이전 포스팅에서 SK, CY으로 그림 상의 테이블을 채웠는데, 이번엔 전자와 후자로 표현하겠다. 그게 더 올바른 의미이기 때문이다.
길이 1000+1의 DP배열을 먼저 만들어둘 수 있다. 이제 그 배열을 0과 1로 채울텐데 편의상 0이면 전자 승(상근이가 먼저 두므로 상근이의 승리) 1이면 후자 승(창영이의 승리)이 되겠다.
그리고 이전 포스팅에서도 거듭 강조했듯이 이 배열을 참조할 때 반드시 숙지할 사항은 3개를 집어가는 예시 DP[i-3]에서는 창영이가 먼저 두는 상황이라는 것이다! DP[i]를 구할때는 상근이가 먼저 두는 상황이지만, 이전 상황의 값을 참조하여 현재 값을 구할때 DP[i-3]이 1이라면 (후자의 승리) 상근이가 이기는 상황인것이다. DP[i-3]에서는 이제 창영이가 먼저두는 상황이 되고, 후자는 상근이기 때문이다.
마지막 돌을 집어가는 사람이 지는 것이므로 현재 돌의 갯수에서 집어간 돌을 뺀 값이 0이되면 진다. 그리고 현재 돌에서 1, 3, 4를 가져간 경우중에 하나라도 후자 승이 있다면 이번 경우에서 승리할 수 있다.
위와 같이 DP[6]의 경우, DP[5], DP[3], DP[2]를 참조하게 되는데 DP[3]으로 가면 후자의 승리이고, 즉 상근이의 승리이다. 완벽한 게임을 한다면 DP[3]으로 가게되고 DP[6]에서는 상근이가 승리한다고 말할 수 있다.
<주요 내용>
다이나믹 프로그래밍
<코드>
Python
n, stones = int(input()), [1, 3, 4]
dp = [0 for _ in range(n+1)]
for i in range(n+1):
flag = False
for stone in stones:
if i-stone <= 0:break
if dp[i-stone]:
flag = True
break
if not flag:dp[i] = 1
print('CY' if dp[n] else 'SK')
