(LeetCode) 877. Stone Game

문제 링크

• LeetCode

요약

• LeetCode 486 과 같은 문제

최종 §

결과

• LeetCode 486 과 같은 방식으로 접근해서 풀면 된다.

#define SUM(acc, l, r) ((acc)[(r) + 1] - (acc)[(l)])
 
class Solution {
	array<array<int, 500>, 500> dp;
	array<int, 501> acc;
public:
	bool stoneGame(vector<int>& piles) {
		int n = piles.size();
 
		acc[0] = 0;
		for (int i = 0; i < n; i++) {
			acc[i + 1] = acc[i] + piles[i];
		}
 
		for (int i = 0; i < n; i++) {
			dp[i][i] = piles[i];
		}
 
		for (int x = 1; x < n; x++) {
			for (int i = 0; i + x < n; i++) {
				int j = i + x;
				int take_i = piles[i] + (SUM(acc, i + 1, j) - dp[i + 1][j]);
				int take_j = piles[j] + (SUM(acc, i, j - 1) - dp[i][j - 1]);
 
				dp[i][j] = max(take_i, take_j);
			}
		}
 
		return dp[0][n - 1] > (SUM(acc, 0, n - 1) - dp[0][n - 1]);
	}
};