[c++] 백준 30108 교육적인 트리 문제

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

30108번: 교육적인 트리 문제

이 문제를 푸는 방법은 두 가지이다.

자식 노드의 값이 부모 노드의 값보다 같거나 작다는 조건을 이용할 것인가 안 할 것인가로 나뉜다.

 

1. 이용하지 않을 때

문제를 처음 보고 알 수 있는 것은

(선택된 모든 정점은 루트 정점이거나, 자신의 부모 정점 또한 선택되어 있어야 한다)라는 문제 조건에 의해

정점을 선택할 때 트리의 루트부터 선택하여 그의 자식들 중 하나를 선택해야 한다는 점이다.

 

이걸 바탕으로 생각해 보면 그리디 알고리즘임을 눈치챌 수 있고,

항상 최선의 방법을 선택하는 것이 정답임을 알 수 있다.

 

항상 최선인 것을 관리하기 위해 우선순위 큐를 사용한다.

우선순위 큐 top의 정점을 선택하여

그 정점의 값을 변수에 누적시키면서 출력하고 우선순위 큐에서 빼준다.

우선순위 큐에 선택한 정점의 자식들을 넣어주며 우선순위 큐가 빌 때까지 반복한다.

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<ll> tree[300300];
ll a[300300], n;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n;
    for(ll i=2; i<=n; i++){
        ll k; cin>>k;
        tree[k].push_back(i);
    }
    for(ll i=1; i<=n; i++)
        cin>>a[i];
    priority_queue<pair<ll,ll>> pq;
    pq.push({a[1],1});
    ll ans=0;
    while(!pq.empty()){
        ll val,node;
        tie(val,node) = pq.top();
        pq.pop();
        ans += val;
        cout << ans << '\n';
        for(auto next : tree[node])
            pq.push({a[next],next});
    }
    return 0;
}

2. 이용할 때

처음 언급한 문제 조건을 생각해 보면

내림차순으로 주어진 정점들의 값을 정렬하였을 때

앞에 있는 값이 항상 뒤에 있는 값의 부모 정점 관계임을 알 수 있다.따라서 주어진 값들을 내림차순 정렬 후 누적한 값을 출력하면 된다.

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,trash,ans;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n;
    vector<ll> v(n);
    for(int i=1; i<n; i++) cin>>trash;
    for(auto &i : v) cin>>i;
    sort(v.rbegin(),v.rend());
    for(auto i : v){
        ans += i;
        cout << ans << '\n';
    }
    return 0;
}