BOJ 14657 준오는 최종인재야!!

준오는 최종인재야!!

(http://boj.kr/14657)

대회 때는 문제 자체도 이해하기 힘들었는데, 지금 다시 보니 트리의 지름 문제와 매우 비슷했다.

처음에 설명하는 문제 풀이 시스템은 사실 트리의 설명이다. 그리고 트리에서 가장 긴 경로(트리의 지름)을 찾는 것이다.

트리의 지름 문제와 다른 점은, 이 문제에서는 지나는 노드의 개수를 최대로 하면서 가중치는 따로 계산해야 한다.

트리의 지름을 구할 때는 아무 점이나 잡고 그 점에서 가장 먼 점 u를 찾고, u에서 가장 먼 점 v를 찾으면 u에서 v로 가는 경로가 트리의 지름이다.

그렇게 구현하니 맞기는 했는데, 저게 되는 이유가 잘 이해되지 않아서 그냥 모든 노드에서 자신이 지름에 포함되는 경우를 보도록 다시 구현했다.

n = 2인 경우도 잘 고려해야 한다.

#include <bits/stdc++.h>
 
using namespace std;
 
vector<pair<int, int> > gph[50001];
int mxd = -0x80000000, mn = 0x7fffffff;
 
bool cmp(vector<int> a, vector<int> b) {
    if (a[0] == b[0])
        return a[1] < b[1];
    return a[0] > b[0];
}
 
vector<int> f(int now, int prv) {
    if (gph[now].size() == 1)
        return { 0, 0 };
 
    if (gph[now].size() == 2 && prv != -1) {
        vector<int> ret;
 
        if (gph[now][0].first != prv) {
            ret = f(gph[now][0].first, now);
            ret[0]++;
            ret[1] += gph[now][0].second;
        }
        else {
            ret = f(gph[now][1].first, now);
            ret[0]++;
            ret[1] += gph[now][1].second;
        }
 
        return ret;
    }
 
    vector<vector<int> > v;
 
    for (pair<int, int> t : gph[now])
        if (t.first != prv) {
            vector<int> temp = f(t.first, now);
            temp[0]++;
            temp[1] += t.second;
 
            v.push_back(temp);
        }
 
    sort(v.begin(), v.end(), cmp);
 
    if (v[0][0] + v[1][0] > mxd) {
        mxd = v[0][0] + v[1][0];
        mn = v[0][1] + v[1][1];
    }
    else if (v[0][0] + v[1][0] == mxd)
        if (mn > v[0][1] + v[1][1])
            mn = v[0][1] + v[1][1];
 
    return v[0];
}
 
int main() {
    int n, t, i, u, v, w;
 
    scanf("%d %d", &n, &t);
 
    for (i = 1;i < n;++i) {
        scanf("%d %d %d", &u, &v, &w);
 
        gph[u].push_back({ v, w });
        gph[v].push_back({ u, w });
    }
 
    for (i = 1;i <= n;++i)
        if (gph[i].size() > 1) {
            f(i, -1);
            break;
        }
 
    printf("%d", n == 2 ? gph[1][0].second / t + (gph[1][0].second % t ? 1 : 0) : mn / t + (mn % t ? 1 : 0));
 
    return 0;
}