[BAEKJOON] 14657. 준오는 최종인재야!!

Posted on March 15, 2021

문제 :

심술쟁이 해커 임준오(동탄 주민)는 BOB에 불합격했다. 아주인싸 해커 이시훈(김포 주민)과 함께 KFC 숙대입구역점에서 햄버거를 먹다가 지원마감 시간이 지나버렸기 때문이다! 하지만 걱정하지 마시라. 준오는 1년의 기다림을 지나 BOB에 합격했다.

재수 끝에 기회를 잡은 준오는 꼭 최종인재가 되기로 결심했다. 하지만 안티준오 멘토 김영중(장평 주민)은 준오를 최종인재로 추천하고 싶지 않았다. 그래도 멘토는 공정해야 하기 때문에, 영중이는 준오에게 악랄한 과제를 내주기로 했다.

“네가 만약 제한 시간 안에 기준치 이상의 문제를 풀어온다면 너를 최종인재로 추천해주겠다. 하지만 그렇지 못한다면! 너는 영원히 BOB 센터에서 히어로즈 오브 더 스톰을 플레이해야 할 거야… 후후”

진정한 최고 해커라면 선택의 길에 운도 따라야하는 법. 영중이가 고안한 문제 풀이 시스템은 다음과 같다.

N개의 문제들과 임의의 두 문제를 연결하는 링크가 N-1개 존재한다. (링크는 양방향으로 동작한다)
N개의 문제들 중 링크를 통해 도달할 수 없는 문제는 없다.
임의의 문제 A에서 B까지 도달하는 경로는 유일하다.

준오는 N개의 문제들 중 원하는 문제를 하나 골라서 테스트를 시작할 수 있다. 한 번 테스트를 시작하면 문제를 바꿀 수 없으며, 문제를 푼 이후에는 해당 문제에 연결된 링크들 중 하나를 골라 문제를 선택할 수 있다. 단, 문제를 풀고 난 후 링크를 통해 한 번 문제를 선택하고 나면, 이전에 풀었던 문제로 다시 돌아갈 수는 없다. 어떤 문제 A에 연결된 문제 B와 C가 있을 때, A를 풀고 나서 B를 푸는 시간과 A를 풀고 나서 C를 푸는 시간이 각각 다를 수 있다. 물론 B를 풀고 A를 푸는 시간은 A를 풀고 B를 푸는 시간과 동일하다. 처음 고른 문제는 보너스로 취급되어 무조건 정답처리 된다. 다시 말해, 첫 번째 문제를 푸는 데에는 0초의 시간이 소요된다.

준오는 영중이가 굉장히 건방지다고 생각했고, 화가 난 준오는 과제 따위는 잊어버리고 영중이의 시스템 내에서 풀 수 있는 최대한의 문제를 풀어 보이려고 한다. 하지만 준오도 사람이기 때문에 하루에 문제 풀이에 투자할 수 있는 시간은 정해져있다. 그래서 준오는 매일 투자할 수 있는 최대한의 시간 동안 문제를 풀고, 남은 문제는 그 다음날에 이어서 풀려고 한다. 예를 들어, 준오가 하루에 4시간을 투자할 수 있고 a->b->c->d를 푸는 시간이 모두 3이라면, 문제를 푸는데 걸리는 시간은 3+3+3=9가 되고 걸리는 날짜 수는 4+4+1=9로 3일이 된다.

당신은 딱히 궁금하지 않겠지만, 아무튼 문제가 이렇게 나왔으니 궁금하다고 치자. 당신은 준오가 최대한 많은 문제를 푸는 데 며칠이나 걸릴 지 궁금해졌다! 문제의 수 N, 하루에 문제 풀이에 투자할 수 있는 시간 T, 연결된 문제의 정보가 주어질 때, 준오가 시스템 내에서 최대한 많은 문제를 푸는 데 걸리는 최소의 날짜 수를 계산해보자!

입력 :

첫째 줄에 문제의 수 N, 하루 풀이 시간 T가 주어진다. (2 <= N <= 50,000, 1 <= T <= 100,000) 이후 둘째 줄 부터 N-1개의 줄에 걸쳐 각 줄마다 A, B, C가 주어진다. (1 <= A, B <= N, 1 <= C <= 1,000) A와 B는 서로 연결된 문제의 번호를 뜻하며, C는 A를 풀고 B를 풀거나 B를 풀고 A를 푸는데 걸리는 시간을 뜻한다.

출력 :

풀이 :

우선 준오가 풀어야 할 문제들의 연결 상태를 보게 되면 트리 형태로 연결되있는 것을 확인할 수 있다.

따라서, 가장 많은 문제를 푸는 경우는 트리의 지름을 구하면 가능하다고 생각했다.

트리의 지름에서 소요되는 시간을 하루 가능 작업량으로 나누면 문제르 해결할 수 있었다.

코드 :

코드 보기/접기

#include <iostream>
#include <vector>
#include <utility>

#define pii pair<int, int>
#define MAX 50001

using namespace std;
vector<vector<pii>> adj;
bool visit[MAX];
int maxcnt, mintime = 987654321, maxidx;

void dfs(int curidx, int curcnt, int curtime) {
    visit[curidx] = true;

    int size = adj[curidx].size();
    for (int k = 0; k < size; k++) {
        if (visit[adj[curidx][k].first]) continue;
        dfs(adj[curidx][k].first, curcnt + 1, curtime + adj[curidx][k].second);
    }
    if (maxcnt < curcnt || (maxcnt == curcnt && mintime > curtime)) {
        maxcnt = curcnt;
        mintime = curtime;
        maxidx = curidx;
    }

    visit[curidx] = false;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n, t, fir, sec, val, answer;
    cin >> n >> t;
    adj.resize(n + 1);
    for (int i = 1; i < n; i++) {
        cin >> fir >> sec >> val;
        adj[fir].emplace_back(sec, val);
        adj[sec].emplace_back(fir, val);
    }

    dfs(1, 1, 0);
    dfs(maxidx, 1, 0);

    answer = mintime / t + ((mintime % t > 0) ? 1 : 0);
    cout << answer << '\n';
    return 0;
}

Algorithm

algorithm baekjoon C++