❓ Question
📖 Before Start
동적 프로그래밍은 정말 종류가 다양하게 나와서 매번 머리가 아프다.
DP (Dynamic Programming) 문제를 어느덧 20개 이상 접하였지만, 아직도 점화식을 세울때마다 머리가 아픈 건 어쩔 수 없나보다.
더 많이 깨지고 부셔져야 문제를 푸는 직관력이 늘어나겠지만, 그래도 답이 안나올때 짜증이 나는 건 어쩔 수 없나보다.
✒️ Design Algorithm
처음엔 완벽하게 게임을 끝냈다는 의미가 무엇인지를 이해하지 못했다.
따라서 나는 정말 단순하게 돌을 빨리 가져갈 수 있는 알고리즘을 설계하면 되지 않을까? 라는 생각을 했었다.
그래서 돌이 N개 놓였을 때. dp[N] 은 N개의 돌을 모두 가져가는 데 필요한 최소한의 횟수로 가정하고 점화식을 작성하였다.
아래는 필자가 문제를 풀기 전 작성한 알고리즘 설계이다.
N개의 돌을 모두 가져가는 데 걸린 횟수를 메모이제이션에 저장한다.
점화식은 dp[i] = min(dp[i-1], dp[i-3], dp[i-4]) + 1로 놓고 반복을 진행.
- 첫 번째 줄에는 게임 진행에 필요한 돌의 갯수
N입력된다. - 그 후 1번째, 3번째, 4번째의 경우 최소 횟수가 1회이므로 이를 초기화한다.
💻 Making Own Code
❌ Wrong Code
import sys
from math import inf
n = int(sys.stdin.readline())
dp = [inf, 1, 2, 1, 1] + [0] * (n-4)
for i in range(5, n+1):
dp[i] = min(dp[i-1], dp[i-4], dp[i-3]) + 1
print('SK' if dp[n] % 2 == 0 else 'CY')하지만 6을 입력하면, 케이스의 답인 SK가 아닌 CY을 출력하는 것이 아닌가?
여기서부터 나의 내적 혼돈이 시작되었다, 대체 완벽하게 게임을 끝낸다는 것이 무슨 의미인 걸까?
그래서 한참을 고민하다 결국 힌트를 보았지만, 이 문제를 완전히 이해하기까지 제법 시간이 걸렸다.
게임을 완벽하게 끝낸다는 건, 현재 턴을 진행하는 사람이 절대 질 수 없는 상황 을 만드는 것이다.
즉 매 순간마다 자신의 승리를 위한 최적의 수 를 둔다는 의미지, 빨리 게임을 끝내는 의미가 아니었다.
✅ Correct Code
import sys
n = int(sys.stdin.readline())
dp = [None, 'SK', 'CY', 'SK', 'SK'] + [0] * (n-4)
for i in range(5, n+1):
if dp[i-1] == 'SK' and dp[i-3] == 'SK' and dp[i-4] == 'SK':
dp[i] = 'CY'
else:
dp[i] = 'SK'
print(dp[n])따라서 나는 메모이제이션과 점화식을 다시금 설계해야만 했다. 후에 내가 내린 결론은 아래와 같다.
현재 돌이 N개인 상황에서, 돌을 1, 3, 4개 넘겼을 때 후수가 이길 수 있는 경우를 보자.
만약 테이블 위에 돌이 N개 남았다고 가정해보자. 나의 턴이 왔다면 아래의 추론을 진행할 수 있다.
- 상근이가 돌을 1, 3, 4개 가져갔을 때, 남은 돌 N-1, N-3, N-4 개에 대한 승패를 확인한다.
- 만약 창용이 이긴 전적이 세 가지 케이스 중 한개라도 존재한다면 이번 게임은 상근이 승리한다.
❓ 왜 이런 결론을 내렸는가?
필자는 상근이가 돌을 1개, 3개, 혹은 4개를 넘기고 자신이 선수가 아닌 후수가 되는 가정을 내렸다.
이럴 경우 남은 돌은 N-1, N-3, N-4 개로 총 세 가지 경우가 생기며, 이때의 선수는 창용이 된다.
그 후 남은 돌을 가지고 게임을 하였을 때, 셋 중 하나라도 후수 가 이긴 경우가 있는지를 본다.
만약 N = 5 일 경우, 상근이 고려할 케이스는 N = 1, N = 2, N = 4 로 총 세 가지다.
이 중에서 N = 2 일 경우 후수인 창용이 이기므로, 상근이는 돌을 3개 넘기고 후수를 자처하면
이 게임에서 무조건 이길 수 있는 최선의 선택을 한 것이다. (막상 쓰면서도 이해가 참 어렵다...)
결론은, 상근이를 후수로 놓고 케이스를 조회하여 후수가 승리할 수 있는 경우가 있는지를 판별해야 한다.
상근이 가져갈 수 있는 돌은 1개, 3개, 4개 니, 남은 돌이 N-1, N-3, N-4 일 때 후수가 이기는 경우를 보면 된다.
동적 프로그래밍은 이래서 참 까다롭다. 점화식을 세우는 과정이 너무 험난하지 않은가?
이번 문제도 만만하게 보고 덤볐다 꽤나 이해하는데 애를 먹었다. 더 많은 연습이 필요해보인다.
