숫자로 이루어진 리스트 nums가 있다고 가정해 보겠습니다. 여기서 허용되는 연산은 인접한 두 값을 골라 그 합으로 하나의 값으로 병합하는 것입니다. 이때 리스트 전체가 비증가(non-increasing) 상태, 즉 왼쪽에서 오른쪽으로 갈수록 값이 커지지 않는 형태가 되도록 만들어야 하며, 필요한 최소 연산 횟수를 구하는 것이 이 문제의 목표입니다.
예를 들어 입력이 nums = [2, 6, 4, 10, 2]라고 해 보겠습니다. 먼저 [2, 6]을 합쳐 [8, 4, 10, 2]를 만들고, 이어서 [8, 4]를 합쳐 [12, 10, 2]를 만들면 리스트가 비증가 상태가 됩니다. 따라서 정답은 2입니다.
접근 방법: 동적 계획법(DP)
이 문제는 리스트를 뒤에서부터 처리하는 동적 계획법으로 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- dp[i] : i번째 위치부터 끝까지 비증가 형태로 만들기 위해 필요한 최소 병합 횟수
- arr[i] : i번째 위치부터 병합을 진행했을 때 해당 자리에 최종적으로 남게 되는 값
리스트 맨 뒤에 음의 무한대(-inf)를 추가하면 경계 조건 처리가 한결 간단해집니다. 마지막 원소는 항상 어떤 값보다도 작으므로, while 반복문 안에서 범위 초과 여부를 별도로 검사하지 않아도 되기 때문입니다.
알고리즘 단계
- nums가 비어 있으면 0을 반환합니다.
- nums의 끝에 -inf(음의 무한대)를 삽입합니다.
- N := nums의 크기로 설정합니다.
- dp와 arr을 각각 크기 N의 리스트로 만들고 0으로 초기화합니다.
- p := arr의 크기
- arr[p-1] := nums[N-1], arr[p-2] := nums[N-2]로 설정합니다.
- i를 N-3부터 0까지 1씩 감소시키며 반복합니다.
- j := i, x := nums[j]
- j < N-1이고 x < arr[j+1]인 동안 j를 1 증가시키고 x에 nums[j]를 더합니다. (현재 값이 뒤의 값보다 작으면 계속 병합)
- dp[i] := j - i + dp[j+1] 로 병합 횟수를 갱신합니다.
- arr[i] := x 로 병합 결과값을 저장합니다.
- 최종적으로 dp[0]을 반환합니다.
구현 예제
class Solution:
def solve(self, nums):
if not nums:
return 0
nums.append(float("-inf"))
N = len(nums)
dp = [0] * N
arr = [0] * N
arr[-1] = nums[-1]
arr[-2] = nums[-2]
for i in range(N - 3, -1, -1):
j = i
x = nums[j]
while j < N - 1 and x < arr[j + 1]:
j += 1
x += nums[j]
dp[i] = j - i + dp[j + 1]
arr[i] = x
return dp[0]
ob = Solution()
nums = [2, 6, 4, 10, 2]
print(ob.solve(nums))
입력
[2, 6, 4, 10, 2]
출력
2
동작 원리 살펴보기
입력 [2, 6, 4, 10, 2]에 대해 알고리즘이 어떻게 동작하는지 간단히 살펴보겠습니다. 리스트 뒤에 -inf를 붙이면 [2, 6, 4, 10, 2, -inf]가 됩니다. 이후 뒤에서부터 앞으로 탐색하면서, 현재 위치의 값이 다음 위치의 값(arr 배열 기준)보다 작으면 조건을 만족할 때까지 계속 병합을 진행합니다. 각 위치에서 발생한 병합 횟수를 dp 배열에 누적하면, 최종적으로 dp[0]에 전체 리스트를 비증가 형태로 만드는 데 필요한 최소 연산 횟수인 2가 저장됩니다.
이 알고리즘의 시간 복잡도는 최악의 경우 O(N²), 공간 복잡도는 O(N)입니다. 리스트가 길어질수록 병합 연산 횟수를 일일이 시뮬레이션하는 것보다 훨씬 효율적으로 답을 구할 수 있다는 점이 이 접근 방식의 장점입니다.