문제 설명
문자열의 위치를 나타내는 브레이크포인트(breakpoints)라고 불리는, 중복 없이 정렬된 숫자 목록이 있다고 가정해 보겠습니다. 이 값들을 사용해 아래 규칙에 따라 하나의 트리를 만들려고 합니다.
- (a, b) 형태의 값을 가지는 노드가 존재하며, a와 b는 브레이크포인트입니다. 즉, 해당 노드는 문자열에서 [a, b] 구간을 담당합니다.
- 루트 노드는 전체 문자열, 즉 모든 브레이크포인트 범위를 포괄합니다.
- 노드의 왼쪽 자식과 오른쪽 자식의 구간은 순서대로 배치되고 서로 연속적이며, 두 구간을 합치면 부모 노드의 구간이 됩니다.
- 리프 노드의 경우, 브레이크포인트 배열에서 'b'의 인덱스 바로 앞이 'a'의 인덱스여야 합니다.
트리의 비용은 트리를 구성하는 모든 노드에 대해 (b − a) 값을 더한 것으로 정의됩니다. 따라서 우리의 목표는 위 조건을 만족하는 트리 중에서 비용이 가장 작은 경우를 찾는 것입니다.
예를 들어 입력이 breakpoints = [1, 4, 7, 12]라면 출력은 28이 됩니다.
접근 방법
이 문제는 구간 단위로 최적해를 쌓아 올리는 구간 동적 계획법(Interval DP)으로 해결할 수 있습니다. 여기에 분할 지점 탐색 범위를 좁혀 주는 크누스 최적화(Knuth Optimization)를 적용하면 불필요한 탐색을 줄여 효율적으로 답을 구할 수 있습니다.
풀이 절차
- n을 입력 배열 breakpoints의 크기로 설정합니다.
- n ≤ 1이면 0을 반환합니다.
- n == 2이면 breakpoints[1] − breakpoints[0]을 반환합니다.
- 길이가 n−1인 배열 p를 정의하고, p[i] := breakpoints[i+1] − breakpoints[i]로 채웁니다. (인접한 브레이크포인트 사이의 거리)
- 길이가 n인 배열 pre를 정의하고, pre[i] := pre[i−1] + p[i−1]로 누적합을 계산합니다.
- 2차원 배열 dp[n][n]을 선언하고 모든 값을 무한대(INT_MAX)로 초기화합니다.
- 2차원 배열 op[n][n]을 선언합니다. op에는 각 구간의 최적 분할 지점이 저장됩니다.
- i = 1부터 n−1까지 dp[i][i] := p[i−1], op[i][i] := i로 설정하여 길이 1인 구간의 초기값을 만듭니다.
- len = 2부터 n−1까지 반복하며 다음을 수행합니다.
- j := i + len − 1로 구간의 끝을 계산합니다.
- k를 max(i, op[i][j−1])부터 min(j−1, op[i+1][j])까지 탐색하면서 cost := dp[i][k] + dp[k+1][j]를 구하고, 기존 dp[i][j]보다 작으면 idx := k로 갱신합니다.
- op[i][j] := idx를 저장합니다.
- dp[i][j] += pre[j] − pre[i−1]로 구간 전체 길이를 더해 최종 비용을 완성합니다.
- 마지막으로 dp[1][n−1]을 반환합니다.
예제 코드
이해를 돕기 위해 아래 C++ 구현을 살펴보겠습니다.
#include <bits/stdc++.h>
using namespace std;
int solve(vector<int>& breakpoints) {
int n = breakpoints.size();
if (n <= 1) return 0;
if (n == 2) return breakpoints[1] - breakpoints[0];
vector<int> p(n - 1);
for (int i = 0; i < n - 1; ++i) p[i] = breakpoints[i + 1] - breakpoints[i];
vector<int> pre(n);
for (int i = 1; i < n; ++i) pre[i] = pre[i - 1] + p[i - 1];
vector<vector<int>> dp(n, vector<int>(n, INT_MAX));
vector<vector<int>> op(n, vector<int>(n));
for (int i = 1; i < n; ++i) dp[i][i] = p[i - 1], op[i][i] = i;
for (int len = 2; len < n; ++len) {
for (int i = 1; i + len - 1 < n; ++i) {
int j = i + len - 1;
int idx = i;
for (int k = max(i, op[i][j - 1]); k <= min(j - 1, op[i + 1][j]); ++k) {
int cost = dp[i][k] + dp[k + 1][j];
if (cost < dp[i][j]) {
idx = k;
dp[i][j] = cost;
}
}
op[i][j] = idx;
dp[i][j] += pre[j] - pre[i - 1];
}
}
return dp[1][n - 1];
}
int main(){
vector<int> breakpoints = {1, 4, 7, 12};
cout << solve(breakpoints) << endl;
return 0;
}
입력
{1, 4, 7, 12}
출력
28
결과 해설
브레이크포인트 [1, 4, 7, 12]에서 인접 구간의 길이는 각각 3, 3, 5입니다. 리프 노드 세 개의 비용 합은 11이며, 내부 노드들이 상위 구간을 덮으면서 추가되는 비용까지 모두 합산하면 전체 트리 비용은 28이 됩니다.