양의 정수로 이루어진 배열 arr가 주어졌을 때, 다음 조건을 만족하는 모든 이진 트리(binary tree)를 생각해 봅시다.
- 각 노드는 자식을 0개 또는 2개 가집니다.
- 배열
arr의 값들은 트리를 중위 순회(inorder traversal)했을 때 각 리프 노드의 값과 순서대로 일치합니다. - 각 비-리프(non-leaf) 노드의 값은 왼쪽 서브트리의 최대 리프 값과 오른쪽 서브트리의 최대 리프 값을 곱한 것과 같습니다.
이렇게 만들 수 있는 모든 이진 트리 중에서, 비-리프 노드 값들의 합이 가장 작아지는 경우를 찾아야 합니다. 예를 들어 입력 배열이 [6, 2, 4]라면 출력은 32가 됩니다. 이 입력으로 만들 수 있는 트리는 아래 그림처럼 두 가지가 있습니다.
문제 해결 접근 방법
이 문제는 동적 계획법(Dynamic Programming)과 메모이제이션(Memoization)을 활용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 구간 [i, j]를 분할점 k를 기준으로 왼쪽 구간 [i, k]와 오른쪽 구간 [k+1, j]로 나누고, 각 구간에서 만들 수 있는 최소 비용을 재귀적으로 구하는 것입니다. 이때 분할 지점에서 새로 생기는 비-리프 노드의 비용은 왼쪽 구간의 최댓값과 오른쪽 구간의 최댓값의 곱이 됩니다.
구체적인 풀이 단계는 다음과 같습니다.
- 메모이제이션을 위한 딕셔너리
memo를 생성합니다. dp(i, j)메서드를 정의합니다. 이 메서드는 다음과 같이 동작합니다.j <= i이면 구간에 리프가 하나뿐이므로 0을 반환합니다.(i, j)가 이미memo에 저장되어 있다면 해당 값을 반환합니다.res를 무한대(infinity)로 초기화합니다.k를i부터j-1까지 반복하면서 다음을 수행합니다.res = min(res, dp(i, k) + dp(k+1, j) + max(arr[i:k+1]) * max(arr[k+1:j+1]))
- 계산 결과를
memo[(i, j)]에 저장한 후 반환합니다.
- 메인 메서드에서
dp(0, len(arr)-1)을 호출하여 전체 배열에 대한 최소 비용을 구합니다.
구현 예제
class Solution(object):
def mctFromLeafValues(self, arr):
"""
:type arr: List[int]
:rtype: int
"""
self.memo = {}
def dp(i, j):
if j <= i:
return 0
if (i, j) in self.memo:
return self.memo[(i, j)]
res = float('inf')
for k in range(i, j):
res = min(res, dp(i, k) + dp(k + 1, j)
+ (max(arr[i:k+1]) * max(arr[k+1:j+1])))
self.memo[(i, j)] = res
return self.memo[(i, j)]
return dp(0, len(arr) - 1)실행 결과 확인
입력:
[6, 2, 4]
출력:
32
복잡도 분석
이 알고리즘의 시간 복잡도는 구간의 길이와 분할점을 모두 탐색해야 하므로 O(n³)이며, 메모이제이션에 필요한 공간 복잡도는 O(n²)입니다. 배열의 길이가 최대 40으로 제한되는 문제 조건에서는 충분히 빠르게 동작합니다.