민코프스키 합 DP

민코프스키 합 DP, Minkowski Sum DP

정의

민코프스키 합 (Minkowski Sum) 은 두 점 집합 A, B 의 합 A + B = {a + b : a ∈ A, b ∈ B}. 두 볼록 다각형의 민코프스키 합은 각 변을 각도순으로 합친 새로운 볼록 다각형, O(|A| + |B|) 시간.

민코프스키 합 DP 는 트리 DP / 분할정복 DP 에서 자식들의 볼록 frontier (예: x = 정점 수, y = 비용) 를 한 점이 아닌 볼록 다각형 / 위 / 아래쪽 frontier 로 들고 다니면서 부모로 올라갈 때 민코프스키 합으로 합치는 패턴.

문제 상황과 동기

전형적인 트리 DP 에서 dp[v][k] = v 의 서브트리에서 k 개 선택 시 최소 비용 을 계산하면, k 가 최대 N 이므로 O(N²) 시간과 공간이 든다. N=10⁵ 이면 불가능.

그런데 trade-off DP 는 특별하다. k 를 늘릴수록 비용이 증가하지만 증가폭이 감소 (또는 증가) 하는 형태, 즉 dp[v][k] 가 k 에 대해 볼록 (convex) 또는 오목 (concave) 하다.

Naive 접근

모든 k 를 배열로 들고 다니면 O(N²) 메모리와 시간. k 의 범위가 10⁹ 같은 경우 배열 불가.

민코프스키 합의 돌파구

볼록한 함수는 frontier 만으로 완벽히 표현된다. 자식 1 의 frontier 와 자식 2 의 frontier 를 합치면 두 점집합의 민코프스키 합, 즉 두 frontier 의 각 변을 기울기 순으로 정렬해 병합 하면 된다. 각 병합 O(|A| + |B|).

전체 트리에서 모든 frontier 의 점 수 합 이 O(N) 이면 전체 O(N log N) (small-to-large 병합 시).

어디서 쓰이나: “트리에서 K 개 정점 선택 최소 비용”, “K 개 간선 매칭 최소 가중치”, “K 개 작업 선택 최소 시간” 등 trade-off DP 가 K 차원이면 점 하나가 아니라 frontier 전체를 들고 다녀야. 자식 결합 = 민코프스키 합 O(|A| + |B|).

시각화

핵심 아이디어

DP 의 상태에 trade-off (개수 vs 가중치) 가 있을 때, 각 자식의 Pareto frontier 를 점들로 들고 다님. 두 frontier 의 합 = 민코프스키 합 (위 / 아래쪽 hull 의 합).

   y (cost)
   ^
   |  *
   |    *
   |       *  (자식 1 의 frontier)
   |         *
   +-----------------> x (count)

자식 1 + 자식 2:
   각 변의 각도를 정렬 + 머지 -> 새 hull

각 단계 O(|A| + |B|). 트리 전체로는 small-to-large 또는 모든 자식의 frontier 크기 합 으로 O(N) ~ O(N log N).

알고리즘 세부 단계

불변량 (Invariant): 각 정점 v 의 frontier[v] 는 (count, cost) 쌍의 리스트로, count 증가에 따라 cost 증가 기울기가 단조 증가 (볼록성).

병합 규칙: 두 frontier A, B 를 합칠 때:

1. A 와 B 의 각 선분을 기울기 순으로 정렬 (두 pointer merge, O(|A| + |B|))
2. 기울기 순으로 선분을 이어 붙여 새 frontier 생성
3. 중복 기울기가 있으면 cost 최저점만 유지

예제 추적 (작은 트리):

정점 3 (리프): frontier = [(0, 0), (1, 5)]  (0개 선택 비용 0, 1개 선택 비용 5)
정점 4 (리프): frontier = [(0, 0), (1, 3)]

정점 2 (부모):
  A = [(0,0), (1,5)] 의 기울기: [5]
  B = [(0,0), (1,3)] 의 기울기: [3]
  민코프스키 합 기울기 정렬: [3, 5]
  
  새 frontier: 
    (0, 0) -> +3 -> (1, 3) -> +5 -> (2, 8)
  결과: [(0,0), (1,3), (2,8)]

정점 1 (루트): 자식 2 의 frontier + 정점 1 자체 비용...

왜 O(N log N) 인가: 각 정점의 frontier 는 서브트리 크기에 비례. small-to-large 병합으로 각 점이 최대 O(log N) 번 복사됨.

구현

다음은 트리 DP 에서 두 자식의 Pareto frontier 를 병합하는 핵심 함수. 각 frontier 는 vector<pair<int, long long>> 로 (count, cost) 쌍의 리스트.

// O(|A| + |B|), O(|A| + |B|) 메모리 (두 볼록 frontier 의 민코프스키 합)
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

// frontier 는 [(cnt, cost)] 로 정렬 (cnt 증가). 볼록 (기울기 단조 증가).
vector<pair<int, ll>> merge_frontiers(
    const vector<pair<int, ll>>& A,
    const vector<pair<int, ll>>& B
) {
    vector<pair<int, ll>> result;
    int i = 0, j = 0;
    int cnt = 0;
    ll cost = 0;

    // 두 frontier 의 각 선분 기울기를 two-pointer 로 병합
    while (i < (int)A.size() || j < (int)B.size()) {
        ll slopeA = (i + 1 < (int)A.size())
            ? (A[i+1].second - A[i].second) / (A[i+1].first - A[i].first)
            : LLONG_MAX;
        ll slopeB = (j + 1 < (int)B.size())
            ? (B[j+1].second - B[j].second) / (B[j+1].first - B[j].first)
            : LLONG_MAX;

        if (slopeA <= slopeB) {
            // A 의 다음 선분이 더 완만 (기울기 작음)
            if (i + 1 < (int)A.size()) {
                int dcnt = A[i+1].first - A[i].first;
                ll dcost = A[i+1].second - A[i].second;
                cnt += dcnt;
                cost += dcost;
                result.push_back({cnt, cost});
                i++;
            } else break;
        } else {
            if (j + 1 < (int)B.size()) {
                int dcnt = B[j+1].first - B[j].first;
                ll dcost = B[j+1].second - B[j].second;
                cnt += dcnt;
                cost += dcost;
                result.push_back({cnt, cost});
                j++;
            } else break;
        }
    }

    return result;
}

// 트리 DP 예제: 각 정점에 가중치 w[v], 서브트리에서 k 개 선택 최소 비용
vector<pair<int, ll>> frontier[100005];
ll w[100005];
vector<int> adj[100005];

void dfs(int v) {
    frontier[v] = {{0, 0}}; // 0 개 선택, 비용 0

    for (int u : adj[v]) {
        dfs(u);
        frontier[v] = merge_frontiers(frontier[v], frontier[u]);
    }

    // v 자신을 선택하는 옵션 추가: 모든 (cnt, cost) -> (cnt+1, cost+w[v])
    vector<pair<int, ll>> with_v;
    for (auto [cnt, cost] : frontier[v]) {
        with_v.push_back({cnt + 1, cost + w[v]});
    }
    frontier[v] = merge_frontiers(frontier[v], with_v);
}

int main() {
    int N;
    cin >> N;
    for (int i = 1; i <= N; i++) cin >> w[i];
    for (int i = 0; i < N - 1; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
    }
    dfs(1);
    // frontier[1] 에 모든 k 에 대한 (k, min_cost) 저장됨
    for (auto [k, cost] : frontier[1]) {
        cout << "k=" << k << " -> " << cost << "\n";
    }
}

구현 팁

1. 기울기 정수 비교: 나눗셈 대신 cross product (dy2 * dx1 - dy1 * dx2) 로 비교해 부동소수점 오차 회피.
2. 중복 제거: 같은 count 에 여러 cost 가 나올 수 있음. 최저 cost 만 유지.
3. small-to-large: 자식 frontier 를 크기 순으로 병합하면 전체 O(N log N) 보장.

응용

1. 부분 트리에서 K 개 정점 선택의 최소 비용

dp[v][k] = v 의 서브트리에서 k 개 선택 시 최소 비용. k 차원이 볼록 (convex in k) 이면 전체 frontier 를 들고 다님.

2. K 개 매칭 / K 개 작업 선택

각 단계마다 K 가 +1, +2, … 로 늘어남. 민코프스키 합으로 효율화.

3. Aliens Trick 의 보완

Aliens Trick 이 볼록성 + lambda 이분탐색이라면, 민코프스키 합 DP 는 frontier 전체 를 들고 다님. K 값을 모두 알고 싶을 때 후자.

복잡도

작업	비용
두 frontier 의 민코프스키 합	O(
트리 전체 DP	O(N) ~ O(N log N)
frontier 한 점 평가	O(log N) (이분탐색)

DP 상태가 K 에 대해 볼록 이라는 전제가 핵심.

함정

1. 볼록성 확인

f(k) - f(k-1) 가 k 에 대해 단조 (증가/감소) 인지 증명 또는 실험으로 확인. 안 그러면 frontier 가 깨짐.

2. concave / convex 의 부호

최대화면 concave, 최소화면 convex. 합을 위쪽 / 아래쪽 어느 hull 로 들고 다니는지 일관되게.

3. 자식 frontier 의 크기

자식이 많아지면 frontier 크기가 커진다. 서브트리 크기에 비례 하도록 small-to-large 머지로 O(N log N) 보장.

4. 같은 x 좌표

같은 K 에 여러 비용이 있을 수 있다. 최저점만 살리는 projection 후 hull 화.

Aliens Trick 과의 비교

항목	Aliens Trick	민코프스키 합 DP
출력	특정 K 의 답	모든 K 의 frontier
도구	외부 이분탐색 + DP	트리 DP + 민코프스키 합
시간	O(N log V)	O(N log N)
메모리	O(N)	O(N) (총 frontier)

Aliens 는 한 값만 빠르게, 민코프스키 합은 모든 값을 압축 해 들고 다님.

BOJ 연습 문제

번호	제목	링크
BOJ 8987	수족관 3	kokoa-lab
BOJ 17674	특별관광도시	kokoa-lab
BOJ 18477	Jiry Matchings	kokoa-lab

참고

• Aliens Trick
• Slope Trick
• 볼록 다각형 접선 최적화
• Bulldozer Trick