백준 1135 : 뉴스 전하기

문제 링크

트리 dp & 그리디를 이용하여 해결하였다.

dp[i] = i의 간접 혹은 직접 부하에게 모두 전화를 돌리는데 걸리는 시간 으로 정의하고, 자식들의 dp값을 모두 저장한 다음, 내림차순으로 정렬한 후, 차례대로 1,2,...씩 더한 값중 최댓값을 그 노드의 dp값으로 한다. 기본 케이스는 간선이 없을때로, 이때는 0을 리턴하도록 한다.

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <vector>
#include <utility>

using namespace std;

typedef pair<int,int> pii;
typedef long long ll;

const int INF = 21 * 1e8;
const int MAX = 1e9;

int n;

vector<int> dp;
vector<vector<int>> edge;
vector<int> p;

int solve(int x)
{
    int& cur = dp[x];
    if(cur != -1) return cur;

    if(edge[x].empty())
    {
        cur = 0;
        return cur;
    }

    vector<int> temp;

    for(auto next : edge[x])
    {
        temp.push_back(solve(next));
    }

    sort(temp.begin(),temp.end(),greater<int>());

    int tempsize = temp.size();
    for(int i = 0;i<tempsize;i++)
    {
        cur = max(cur,temp[i] + i +1);
    }

    return cur;
}
int main()
{
    ios_base :: sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);

    cin>>n;
    dp = vector<int>(n,-1);
    edge =vector<vector<int>>(n);
    p = vector<int>(n);

    if(n == 1)
    {
        cout<<"0";
        return 0;
    }

    for(int i = 0;i<n;i++)
    {
        cin>>p[i];
        if(p[i] != -1)
        {
            edge[p[i]].push_back(i);
        }
    }

    cout<<solve(0);    
    return 0;
}
​