[Algorithm] cpp 백준 11808번: 마리오와 사악한 키노피오

문제

링크: https://www.acmicpc.net/problem/11808
요약: 루트 1에서 시작·종료하며, 키노피오가 루트가 아닌 K개의 정점을 골라 순서를 정한다. 마리오는 각 구간을 항상 최단경로로 이동한다. 키노피오가 노드와 순서를 최악으로 골랐을 때 총 이동 시간을 최대화한 값을 구한다.

입력/출력

1
2
입력: T, 각 테스트케이스마다 N, K와 2..N의 (부모, 간선가중치)
출력: 각 케이스마다 "Case i: 답" 형식

접근 개요

핵심 관찰: 임의 간선 e = (parent, child)의 자식 쪽 서브트리에 고른 노드 수를 s라 하면, 순서를 적절히 번갈아 배치하면 e를 지나는 횟수의 최댓값은 2·min(s, K+1−s).
따라서 전체 최댓값은 2·∑(간선가중치 w_e · min(s_e, K+1−s_e)). 간선별 s_e의 합이 K가 되도록 트리에서 s_e를 배분하는 문제로 환원된다.
해결 전략: 각 서브트리에서 “정확히 t개를 고를 때 얻는 최댓 기여도"를 DP로 계산하고, 자식 DP를 배낭처럼 병합. 간선 (u,v)의 기여는 t개를 v쪽에서 고를 때 w·min(t, K+1−t)를 더한다.

알고리즘 설계

자료구조: 인접 리스트. 각 정점 u에 대해 dp[u][t] = u의 서브트리에서 정확히 t개를 고를 때의 최댓 기여도.
점화식:
- 자식 v의 부분해 dp[v][t]에 간선 기여 w·min(t, K+1−t)를 더한 배열을 만든 뒤, 현재 dp와 배낭 병합.
- 루트(1)를 제외한 정점 u 자체를 고르는 선택을 1개 추가(비용 없음)로 처리.
최종값: 루트의 dp[K]를 구해 간선 기여 합을 얻고, 왕복 이동 전체 거리는 이를 2배 한 값.
복잡도: O(N·K^2), 메모리 O(N·K). (N≤1000, K≤100에서 충분히 통과)

구현 (C++)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
// 더 많은 정보는 42jerrykim.github.io 에서 확인하세요.
#include <bits/stdc++.h>
using namespace std;

using int64 = long long;
const int64 NEG_INF = -(1LL<<60);

int N, K;
vector<vector<pair<int,int>>> adj;

vector<int64> dfs(int u, int parent) {
    // dp[t] = max contribution within subtree of u when exactly t nodes are chosen in this subtree
    vector<int64> dp(1, 0); // t = 0
    int currentCap = 0;     // current max t index available in dp

    for (auto [v, w] : adj[u]) {
        if (v == parent) continue;

        vector<int64> child = dfs(v, u);

        // child's contribution + edge(u-v) contribution for selecting t in v-subtree
        int childCap = (int)child.size() - 1;
        vector<int64> bestChild(childCap + 1, NEG_INF);
        for (int t = 0; t <= childCap; ++t) {
            int m = min(t, (K + 1) - t);
            bestChild[t] = child[t] + 1LL * w * m;
        }

        // knapsack merge dp with bestChild
        int newCap = min(K, currentCap + childCap);
        vector<int64> ndp(newCap + 1, NEG_INF);
        for (int a = 0; a <= currentCap; ++a) {
            if (dp[a] <= NEG_INF/2) continue;
            for (int b = 0; b <= childCap; ++b) {
                if (a + b > K) break;
                ndp[a + b] = max(ndp[a + b], dp[a] + bestChild[b]);
            }
        }
        dp.swap(ndp);
        currentCap = newCap;
    }

    // Optionally select node u itself (except root 1): increases count by 1 with no local cost
    if (u != 1) {
        int newCap = min(K, currentCap + 1);
        vector<int64> ndp(newCap + 1, NEG_INF);
        for (int t = 0; t <= currentCap; ++t) {
            // do not select u
            ndp[t] = max(ndp[t], dp[t]);
            // select u
            if (t + 1 <= K) ndp[t + 1] = max(ndp[t + 1], dp[t]);
        }
        dp.swap(ndp);
        currentCap = newCap;
    }

    return dp;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T; 
    if (!(cin >> T)) return 0;
    for (int tc = 1; tc <= T; ++tc) {
        cin >> N >> K;
        adj.assign(N + 1, {});
        for (int i = 2; i <= N; ++i) {
            int p, c; 
            cin >> p >> c;
            adj[p].push_back({i, c});
            adj[i].push_back({p, c});
        }

        vector<int64> rootDP = dfs(1, 0);
        int64 best = rootDP[K];              // sum over edges of w * min(s, K+1 - s)
        int64 answer = 2 * best;             // total travel time (round trips across edges)
        cout << "Case " << tc << ": " << answer << '\n';
    }
    return 0;
}