문제
There are several stones arranged in a row, and each stone has an associated value which is an integer given in the array stoneValue.
In each round of the game, Alice divides the row into two non-empty rows (i.e. left row and right row), then Bob calculates the value of each row which is the sum of the values of all the stones in this row. Bob throws away the row which has the maximum value, and Alice's score increases by the value of the remaining row. If the value of the two rows are equal, Bob lets Alice decide which row will be thrown away. The next round starts with the remaining row.
The game ends when there is only one stone remaining. Alice's score is initially zero.
Return the maximum score that Alice can obtain.여러 개의 돌이 한 줄로 놓여 있고, 각 돌에는 정수 값이 하나씩 주어져 있습니다. 각 돌의 값은 배열 stoneValue로 주어집니다.
게임은 다음과 같이 진행됩니다.
매 라운드마다 Alice는 현재 돌의 행을 비어 있지 않은 두 개의 행(왼쪽 행과 오른쪽 행)으로 나눕니다.
그다음 Bob은 각각의 행에 있는 돌들의 값을 모두 더해서, 두 행의 값을 계산합니다.
Bob은 값의 합이 더 큰 행을 버립니다.
그리고 Alice는 남아 있는 행의 값만큼 점수를 얻습니다.
만약 두 행의 값이 같다면, Bob은 Alice에게 어느 행을 버릴지 선택하게 합니다.
다음 라운드는 남아 있는 행을 가지고 계속 진행합니다.
돌이 하나만 남으면 게임이 종료됩니다.
Alice의 초기 점수는 0입니다.
Alice가 얻을 수 있는 최대 점수를 반환하세요.
예시
입력: stoneValue = [6,2,3,4,5,5]
출력: 18
설명:
첫 번째 라운드에서 Alice는 돌의 행을 [6,2,3]과 [4,5,5]로 나눕니다.
왼쪽 행의 합은 11, 오른쪽 행의 합은 14입니다.
Bob은 합이 더 큰 오른쪽 행을 버리고, Alice는 남은 왼쪽 행의 값인 11점을 얻습니다.
현재 점수: 11
두 번째 라운드에서 Alice는 남아 있는 [6,2,3]을 [6]과 [2,3]으로 나눕니다.
이번에는 왼쪽 행의 합이 6, 오른쪽 행의 합이 5이므로 Bob은 왼쪽 행을 버립니다.
Alice는 남은 [2,3]의 값인 5점을 추가로 얻습니다.
현재 점수: 11 + 5 = 16
마지막 라운드에서는 [2,3]을 [2]와 [3]으로 나누는 방법밖에 없습니다.
Bob은 합이 더 큰 오른쪽 [3]을 버리고, Alice는 남은 [2]의 값인 2점을 얻습니다.
최종 점수: 16 + 2 = 18
이제 돌이 하나만 남았으므로 게임이 종료됩니다.
제한
풀이
현재 남아 있는 돌의 구간을 [left, right]라고 하겠습니다.
어떤 위치 k에서 구간을 나누면 왼쪽 구간은 [left, k], 오른쪽 구간은 [k + 1, right]가 됩니다. 왼쪽 구간의 합이 오른쪽 구간의 합보다 작거나 같다면 왼쪽 구간을 남길 수 있고, 반대의 경우에는 오른쪽 구간을 남기게 됩니다.
따라서 가장 단순하게는 모든 구간 [left, right]에 대해 가능한 모든 분할점 k를 확인하는 구간 DP를 생각할 수 있습니다. 그러나 구간의 개수가 O(n^2)이고 각 구간마다 최대 O(n)개의 분할점을 확인해야 하므로 전체 시간 복잡도는 O(n^3)이 됩니다.
이를 최적화하기 위해 각 구간에서 왼쪽 합이 오른쪽 합보다 작거나 같은 마지막 분할점을 이분 탐색으로 찾습니다.
먼저 prefix sum을 사용하면
left_sum = prefix[k + 1] - prefix[left]
right_sum = prefix[right + 1] - prefix[k + 1]이고,
left_sum <= right_sum이라는 조건은 다음과 같이 정리할 수 있습니다.
2 * prefix[k + 1]
<= prefix[left] + prefix[right + 1]따라서
prefix[k + 1]
<= (prefix[left] + prefix[right + 1]) / 2를 만족하는 마지막 위치를 bisect_right를 이용해 찾을 수 있습니다.
이 위치를 boundary라고 하면, boundary 이하의 분할점에서는 왼쪽 구간을 남길 수 있고, boundary보다 큰 분할점에서는 오른쪽 구간을 남기게 됩니다.
이제 각 분할점을 하나씩 확인하는 대신, 두 개의 보조 DP를 사용해 필요한 최댓값을 미리 관리합니다.
best_left(left, right)는 시작점 left를 고정했을 때,
range_sum(left, k) + dp(left, k)의 값을 left <= k <= right 범위에서 최대로 만드는 값을 의미합니다.
즉,
best_left(left, right)
= max(
best_left(left, right - 1),
range_sum(left, right) + dp(left, right)
)로 계산할 수 있습니다.
반대로 best_right(left, right)는 끝점 right를 고정했을 때,
range_sum(k, right) + dp(k, right)의 값을 left <= k <= right 범위에서 최대로 만드는 값을 의미합니다.
따라서
best_right(left, right)
= max(
best_right(left + 1, right),
range_sum(left, right) + dp(left, right)
)로 계산할 수 있습니다.
이를 이용하면 dp(left, right)에서는 가능한 모든 분할점을 직접 확인할 필요가 없습니다.
boundary 이하에서는 왼쪽 구간이 남으므로
best_left(left, boundary)를 확인합니다.
만약 boundary에서 양쪽 구간의 합이 정확히 같다면 오른쪽 구간을 선택하는 것도 가능하므로
best_right(boundary + 1, right)도 함께 확인합니다.
그리고 boundary + 1 이후의 분할점에서는 오른쪽 구간이 남게 됩니다. 첫 번째 해당 분할점은 boundary + 1이고, 이때 오른쪽 구간의 시작점은 boundary + 2이므로
best_right(boundary + 2, right)를 확인합니다.
결과적으로 각 dp(left, right) 상태에서는 분할점을 전부 순회하지 않고, 이분 탐색으로 경계만 찾은 뒤 best_left, best_right를 통해 각 범위의 최댓값을 바로 얻을 수 있습니다.
dp, best_left, best_right는 각각 O(n^2)개의 상태를 가지며, dp에서 경계를 찾기 위해 O(log n)의 이분 탐색을 수행하므로 전체 시간 복잡도는 O(n^2 log n), 공간 복잡도는 캐시와 prefix sum을 포함해 O(n^2)입니다.
