양의 정수로 이루어진 리스트가 주어졌다고 가정해 보겠습니다. 이때 우리는 값이 모두 같고 길이가 t인 연속된 부분 리스트를 제거할 수 있으며, 제거할 때마다 t × t점을 얻습니다. 이 작업은 리스트가 완전히 빌 때까지 원하는 만큼 반복할 수 있습니다. 목표는 이 과정에서 얻을 수 있는 최대 점수를 구하는 것입니다.
문제 예시
입력이 nums = [4, 4, 6, 4, 4]라고 한다면, 출력은 17이 됩니다.
그 이유는 다음과 같습니다.
- 먼저 가운데 있는
6(길이 1)을 제거하여 1 × 1 = 1점을 얻습니다. - 그러면 리스트가
[4, 4, 4, 4]가 되는데, 이를 한 번에 제거하면 4 × 4 = 16점을 얻습니다. - 따라서 총 17점이 최대 점수입니다.
해결 전략: 동적 계획법(DP)
이 문제는 단순히 앞에서부터 제거하는 그리디 방식으로는 최적해를 보장할 수 없습니다. 중간의 다른 숫자를 먼저 제거해서 양쪽의 같은 숫자들을 합친 뒤 큰 덩어리로 제거하는 것이 더 유리한 경우가 있기 때문입니다.
따라서 dp(left, right, t) 함수를 정의합니다. 이 함수는 구간 [left, right]에서, 왼쪽에 이미 붙어 있는 같은 값의 개수가 t개일 때 얻을 수 있는 최대 점수를 반환합니다.
알고리즘 단계
dp(left, right, t)함수를 정의합니다.left > right이면 더 이상 남은 요소가 없으므로 0을 반환합니다.num := nums[left]로 기준 값을 정하고,left2를 이용해 왼쪽부터 연속된 같은 값의 끝 위치를 찾습니다.- 연속된 개수만큼
t에 더하고,left를 다음 위치로 이동시킵니다. - 현재 묶음을 즉시 제거하는 경우의 점수
t² + dp(left, right, 0)를 계산합니다. - 이후 구간에서
nums[mid] == num인 지점을 찾아, 중간 부분을 먼저 처리한 뒤 나중에 합치는 경우dp(left, mid − 1, 0) + dp(mid, right, t)와 비교하여 더 큰 값을 선택합니다. - 메인 함수에서는
dp(0, len(nums) − 1, 0)을 호출해 결과를 출력합니다.
Python 구현 코드
class Solution:
def solve(self, nums):
def dp(left, right, t):
if left > right:
return 0
num = nums[left]
left2 = left
# 왼쪽부터 연속된 같은 값의 범위를 확장
while left2 < right and nums[left2 + 1] == num:
left2 += 1
t += left2 - left + 1
left = left2 + 1
# 현재 묶음을 바로 제거하는 경우
points = t ** 2 + dp(left, right, 0)
# 중간의 같은 값을 활용해 나중에 합치는 경우 탐색
for mid in range(left, right + 1):
if nums[mid] == num:
points = max(points, dp(left, mid - 1, 0) + dp(mid, right, t))
return points
return dp(0, len(nums) - 1, 0)
ob1 = Solution()
print(ob1.solve([4, 4, 6, 4, 4]))입력
[4, 4, 6, 4, 4]
출력
17
동작 원리 정리
핵심 아이디어는 두 가지 선택지를 모두 고려하는 것입니다.
- 즉시 제거: 현재 연속된 묶음을 바로 제거하고 점수를 확정합니다.
- 나중에 합치기: 사이에 있는 다른 숫자들을 먼저 제거한 후, 떨어져 있던 같은 값들을 하나의 큰 묶음으로 합쳐 제거합니다. 묶음의 길이가 길어질수록 점수는 제곱으로 늘어나므로, 이 전략이 더 유리한 경우가 많습니다.
이렇게 재귀 호출과 함께 상태를 비교하며 최댓값을 갱신하는 방식으로, 리스트가 빌 때까지의 모든 경우 중 가장 높은 점수를 효율적으로 구할 수 있습니다.