문제 소개
숫자로 이루어진 리스트 nums가 주어졌을 때, 다음과 같은 연산을 사용할 수 있다고 가정해 봅시다. 리스트의 첫 번째 또는 마지막 요소가 아닌 숫자 하나를 선택해 제거하고, 그 숫자와 양옆에 인접한 두 숫자의 합만큼 점수를 얻습니다. 이 연산은 원하는 만큼 반복할 수 있으며, 우리의 목표는 얻을 수 있는 최대 점수를 구하는 것입니다.
예제로 이해하기
입력이 nums = [2, 3, 4, 5, 6]라고 해봅시다. 최적의 제거 순서는 다음과 같습니다.
- 먼저 5를 선택합니다. 점수는 (4 + 5 + 6) = 15이고, 리스트는 [2, 3, 4, 6]이 됩니다.
- 다음으로 4를 선택합니다. 점수는 (3 + 4 + 6) = 13이고, 리스트는 [2, 3, 6]이 됩니다.
- 마지막으로 3을 선택합니다. 점수는 (2 + 3 + 6) = 11입니다.
따라서 총점은 15 + 13 + 11 = 39가 되며, 이것이 가능한 최대 점수입니다.
접근 방법: 구간 동적 계획법(DP)
이 문제는 전형적인 구간 DP(interval DP) 유형입니다. dp[i][r]을 "i번째 위치부터 r번째 위치까지 구간에서 경계를 제외한 내부 숫자들을 모두 제거했을 때 얻을 수 있는 최대 점수"로 정의합니다. 각 구간에 대해 마지막에 제거할 숫자 k를 정하면, 해당 시점의 점수는 nums[k]와 양옆 경계값(nums[i], nums[r])의 합이 되고, 그 이전 단계는 두 개의 독립적인 부분 구간 [i, k]와 [k, r]로 나뉩니다. 이를 점화식으로 표현하면 다음과 같습니다.
dp[i][r] = max(dp[i][k] + dp[k][r] + nums[k]) + nums[i] + nums[r] (i < k < r)
풀이 단계
- n := nums의 크기로 설정합니다.
- n < 3이면 제거할 수 있는 숫자가 없으므로 0을 반환합니다.
- (n+1) × (n+1) 크기의 2차원 배열 dp를 생성합니다.
- 구간 길이(len)를 3부터 n까지 늘려가며 반복합니다.
- 각 길이에 대해 시작점 i를 1부터 (i + len − 1 ≤ n) 범위까지 이동시키고, 끝점 r := i + len − 1로 설정합니다.
- 마지막 제거 지점 k를 i+1부터 r−1까지 시도하며, curr := dp[i][k] + dp[k][r] + nums[k−1] 값이 현재 ans보다 크면 갱신합니다.
- 최종적으로 ans에 경계값 nums[i−1] + nums[r−1]을 더해 dp[i][r]에 저장합니다.
- 모든 반복이 끝나면 dp[1][n]을 반환합니다.
파이썬 구현 예제
class Solution:
def solve(self, nums):
n = len(nums)
if n < 3:
return 0
dp = [[0] * (n + 1) for _ in range(n + 1)]
for length in range(3, n + 1):
for i in range(1, n - length + 2):
r = i + length - 1
ans = 0
for k in range(i + 1, r):
curr = dp[i][k] + dp[k][r] + nums[k - 1]
if curr > ans:
ans = curr
ans += nums[i - 1] + nums[r - 1]
dp[i][r] = ans
return dp[1][n]
sol = Solution()
nums = [2, 3, 4, 5, 6]
print(sol.solve(nums))
입력
[2, 3, 4, 5, 6]
출력
39
시간 및 공간 복잡도
시간 복잡도: O(n³) — 구간 길이, 시작점, 분할 지점을 결정하는 세 겹의 중첩 반복문을 사용합니다.
공간 복잡도: O(n²) — 모든 구간의 최대 점수를 저장하는 2차원 DP 테이블이 필요합니다.
마무리
이처럼 구간 DP를 활용하면 "어떤 순서로 제거하느냐"에 따라 결과가 달라지는 문제를 체계적으로 해결할 수 있습니다. 핵심은 각 구간에서 마지막에 제거되는 원소를 기준으로 문제를 더 작은 하위 문제로 분할하는 것이며, 이 패턴은 매트릭스 곱셈 순서, 발란스드 BST 구성 등 다양한 알고리즘 문제에도 응용됩니다.