[C++] 뉴스 전하기 (백준 1135번)

https://www.acmicpc.net/problem/1135

 

트리 dp 문제이다.

 

내 자식 정점들 각각에서의의 전파 시간을 계산한 뒤, 그것들을 잘 활용하여 내 정점에서의 전파 시간을 계산하면 된다. 그래서 난 top-down 방식으로 해결했다.

 

내가 1번 정점이고, 자식으로 2번, 3번, 4번 정점을 가지고 있다고 하자.

정점 i로부터의 전파 시간을 f(i)로 정의하자.

f(1)을 구하기 위해서는 일단 f(2), f(3), f(4)이 모두 구해져 있어야 한다. 그리고 나서 어떤 순서로 뉴스를 전파해야 각 정점에서의 뉴스 전파 시간의 최댓값이 가장 작아지는지를 구해야 한다.

어떤 두 수열의 각 원소 쌍의 합의 최댓값을 최소화하기 위해서는 하나는 오름차순, 하나는 내림차순으로 매칭시키면 된다.

즉, 예를 들어 f(2) = 5, f(3) = 2, f(4) = 7이라고 하면, max(f(4) + 0, f(2) + 1, f(3) + 2) 이런식으로 계산하면 된다.

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int n;
vector<vector<int>> a;
vector<bool> vst;

int td(int cur) {
    if (a[cur].empty()) return 1;
    vector<int> tmp;
    for (int nxt: a[cur]) {
        tmp.push_back(td(nxt));
    }
    sort(tmp.begin(), tmp.end(), greater<>());
    int maxt = 0;
    for (int i = 0; i < tmp.size(); i++) {
        maxt = max(maxt, tmp[i] + i);
    }
    return maxt + 1;
}

void solve() {
    cin >> n;
    a = vector<vector<int>>(n);

    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        if (x == -1) continue;
        a[x].push_back(i);
    }

    cout << td(0) - 1 << '\n';
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int T = 1;
    for (int i = 0; i < T; i++) {
        solve();
    }
}

(AC)