[leetcode #1690] Stone Game VII

Problem

Alice and Bob take turns playing a game, with Alice starting first.

There are n stones arranged in a row. On each player's turn, they can remove either the leftmost stone or the rightmost stone from the row and receive points equal to the sum of the remaining stones' values in the row. The winner is the one with the higher score when there are no stones left to remove.

Bob found that he will always lose this game (poor Bob, he always loses), so he decided to minimize the score's difference. Alice's goal is to maximize the difference in the score.

Given an array of integers stones where stones[i] represents the value of the ith stone from the left, return the difference in Alice and Bob's score if they both play optimally.

Leetcode Challenge를 매일 한 문제씩 풀고 있는데 이해하는 데 오랜 시간이 걸리면 "다음에 풀지 뭐"라는 생각으로 넘어간 뒤 Time Travel Ticket을 사용해서 매달 주는 Badge를 받으려고 한다. 지금까지 푼 문제 중 가장 어려웠던 건 Graph 관련 문제였지만,Stone Game 문제도 만만치 않았다. 두 달 전에 나온 이 문제를 지금에야 언급하는 건 August Challenge에 다시 Stone Game이 등장했기 때문이다. (=_=...) 그 전에 풀지 못 한 Stone Game이 기억이 났고 잠이 오지 않는 지금에야 이 문제를 풀려고 애썼다. 나름 제대로 이해했다고 생각하고 풀이를 글로 남겨본다.

Idea

이런 유형의 문제가 대개 그렇듯이, 큰 문제를 잘게 쪼개어 중간 결과를 메모리에 저장하고 더 큰 문제를 풀 때 작은 문제의 결과를 활용하는 것이 정석이다. (Dynamic Programming) Stone Game도 마찬가지로 DP를 활용해야 하는데, DP를 통해 무엇을 저장할 것인가가 가장 큰 관건이라고 할 수 있다. DP를 활용한 문제 중 어려운 것들은 대개 dp에 저장할 수식이 어려운 경우이다.

Stone Game VII 또한 dp에 무엇을 저장해야 할 지 까다로운 편이다. Alice는 점수 차를 최대한 벌리려고 하고 Bob은 점수 차를 최대한 좁히려고 하는데 dp에 과연 무엇을 저장해야 할까? Alice용 dp와 Bob용 dp를 따로 만들어 저장해야 할까?

dp는 의외로 간단한데, 두 player의 점수 차가 최대가 되는 값을 저장하면 된다.

Alice야 목표가 점수를 벌리는 거라 그렇다쳐도, Bob의 경우도 똑같은지 헷갈릴 수 있다. (나도 그랬다.) 하지만 Bob 또한 점수 차를 최대한 좁히기 위해선 Alice와 점수 차가 최대가 되는 선택을 하면 되는 것이다. dp를 저장할 때 왼쪽 또는 오른쪽 돌을 뺀 값에 남은 돌을 사용한 최대 점수 차이 (dp에 저장되어 있음)를 빼주면 Alice와 Bob이 optimal한 선택을 했을 때 점수 차이가 나오게 된다.

i가 왼쪽 돌의 index, j가 오른쪽 돌의 index라 가정할 때,
dp[i][j] = Math.max(total - stones[i] - dp[i+1][j], total - stones[j] - dp[i][j-1])
로 정할 수 있다.
하지만 i를 큰 값에서 작은 값 순으로 iterate한다고 생각하면 이전에 계산한 dp값은 현재 dp값을 계산할 때만 사용되므로 1d array로 dp를 저장할 수도 있다.
dp[i] = Math.max(total - stones[i] - dp[j], total - stones[j] - dp[j-1])

Solution

class Solution {
	public int stoneGameVII(int[] stones) {
		int n = stones.length;
		int[] dp = new int[n]; 
		for (int i=n-2; i >= 0; i--) {
			int total = stones[i];
			for (int j=i+1; j < n; j++) {
				total += stones[j];
				dp[j] = Math.max(total - stones[i] - dp[j], total - stones[j] - dp[j-1]);
			}
		}

		return dp[n-1];
	}
}

Reference

https://leetcode.com/problems/stone-game-vii/
https://dev.to/seanpgallivan/solution-stone-game-vii-3lei