[platinum3] [해설안봄, 분류확인] boj6000 동전 게임

요새 꾸준히 양치기 연습중이라 플레문제는 오랜만에 풀어 게시글도 오랜만에 올린다. 사실 이문제도 몇일전에 풀었는데 이제야 글을 쓴다..

 이 문제는 게임이론은 자명하지만 고민하다가 혹시 세그먼트 트리라면 안 풀어야겠다하고 분류를 확인했는데 dp와 게임이론 밖에 없어서 그냥 진행했다. (사실 몇일전 boj5000 빵 정렬 풀이과정은 다 생각했지만 세그트리가 필요할 것 같았는데 역시나 여서 풀지 못했던 슬픈일이..)  

 사실 그냥 세그먼트 트리, 이분 매칭, scc 등등 그냥 학습하면 그만이지만 사실 요새의 목표는 코테고 골드문제 양치기 중이라 이런 안나올 거 같은 알고리즘을 학습할 여유가 없다..  그래도 꼴에 다이아 찍고 싶은 열망은 있어서  가끔 웰노운 알고리즘의 플레문제 푸는게 제일 베스트인 것 같다.

 

이 문제는 게임이론을 다이나믹 프로그래밍으로 풀면 되는 것으로, 게임이론과 dp의 조합을 처음 경험해봤고 재밌었던 문제였다.

 

각 턴에서   dp[i번째 동전][i + j까지의 동전] = 그 턴에서 i~ i+j까지의 동전을 가져갈때의 그턴 참가자가 얻을 수 있는지금까지 누적된 돈 최댓값 으로 세우면 된다.

이런식으로 생각 할 수 있다. 빨간 색은 상대 턴에서의 동전들이다.

 

그렇다면 어떻게 동전을 최대로 가져갈 수 있을까?  우선 게임이론 문제이므로, 서로가 동전을 최대한 가져가려고 애를 쓸 것이다. 

따라서 상대도 돈을 최대로 가져가려고 할 것이므로, 다음턴(빨강)에서 동전을 최대한 가져가려고 할 것이다.

그렇다면 그림에서도 확인 할 수 있겠지만,  i~ N 번째까지의 동전들에서  빨간색 부분(다음턴에서부터 게임이 끝날때까지 상대가 가져가는 동전 최댓값) 을 빼면 파란색 부분(이 턴부터 게임이 끝날때까지 내가 가져가는 동전 최댓값) 이 된다.

결국 그러면 dp[i][i + j] = sum[i][N] - dp[i + j + 1][???]   로 점화식을 세울 수 있다. 

현재 플레이어가 가져갈 수 있는 최선은  i~N까지의 동전합에서 다음 턴에서 상대가 가져갈 수 있는 최댓값을 뺀 것이라는 뜻이다.

현재의 플레이어는 j값을 조정하면서  j가언제일때 dp가 최대가 될지 최선의 선택을 할 것이다.

 

??? 부분은 무엇일까. 처음엔  이턴에서 참가자가 k개 ((i + j) - i + 1) 를 가져간다면, 다음 참가자는 1~2 * k 개를 가져갈 수 있으니 dp[i + j + 1][ i + j + 2] 부터 dp[i + j + 1][i + j + 1 + (2*k - 1)] 개를 모두 순회해야 하는 건가? 라고 생각했다. 사실 이부분에서 좀 해맸다.  저렇게 모두 탐색한다면 O(N ^ 3)으로 시간초과다.

고민한 결과 이 부분은 그리디에서 많이 쓰이는 방식으로 해결할 수 있었다. 

사실 참가자가 그턴에 동전을 더 많이 가져갈 수록 dp값이 커지는 건 아니다. 즉 그 턴에 더 많이 != 최선의 결과 이다.

그렇지만 1~2*k 를 가져갈 때 k값이 커질 수록, 더 최선의 결과가 발생할 수도 있는 건 확실하다. 

만약 그턴에 8개를 가져가는게 결과적으로 최선이었다면,  1~12에선 8개를 가져갈 수 있지만 1 ~4에선 불가능 한 것처럼.

1~8 에서 도 가능하고, 1~12에서도 가능하다. 이 경우는 둘다 8을 포함하므로 둘다 최선이다. 

즉 가져갈 수 있는 범위가 (k)가 커질수록  범위가 작을때보다 반드시 나은 상황이라는 것이다.

 

그럼 dp의 의미를 수정해서  dp[i + j + 1][i + j + 1 + (2*k - 1)]  은    그턴에 2*k를 가져갈때 동전최댓값이 아닌,  1~2*k 범위에서 가져갈 때 동전 최댓값으로 수정할 수 있다.

 만약  K를 가져갈 때가 K- 1를 가져갈때보다 손해라면,   dp[i + j + 1][i + j + 1 + (K - 1)]  = dp[i + j + 1][i + j + 1 + ((K - 1) - 1)]   로 설정이 가능하다. 즉  dp에서 k값이 커질수록 무조건 최선이상이라는 것을 알고 있다면, 

dp[i][i + j] = sum[i][N] - dp[i + j + 1][???]  여기서 ??? 의 빈칸 을 채울 수 있다.

dp[i][i + j] = sum[i][N] - dp[i + j + 1][i + j +(2 * j + 2) ]  이다.    dp[i][i + j] 에선 1~(j + 1)범위에서 가져가고, 

dp[i + j + 1][i + j +(2 * j + 2) ] 에선   1 ~(2* j + 2) 의 범위에서 가져간다.

따라서 O(N ^ 2)로 가능하다.

위의 점화식대로 N번째부터 1번째까지 순회하면서  i번째 일때  dp[i][i + 1]부터 dp[i][N] 까지 구해나가면, O(N^2)으로 구할 수 있다.

 

전체동전에서 상대의 최댓값을 뺀다는 아이디어는 생각하기 어렵지 않았지만, 의외로 범위로 수정해 k가 커지면 무조건 dp도 커진다는 발상이 나오는게 좀 오래걸렸다. 사실 되게 스탠다드한 기법인데 말이다..

 

어쨌든 복잡하지만 참신하고 재밌던 게임이론 dp문제였다.

3000 + 3000 만큼 사랑해.. boj6000