2022 구글 코드잼 Qualification Round 후기

A,B,C는 쉬운 난이도의 구현, 그리디 문제였는데 내가 아직 for문에 대한 이해도가 낮구나를 깨달았다. 

 

A구현이 한번에 되지 않고, 시행착오를 겪으면서 구현하였다. 

B에서도 마찬가지 

 

 

 

D가 재밌던 문제라고 느껴졌다. 

 

처음에 bfs로 리프부터 탐색을 할까 거리를 구하는 문제인가 생각하다가 

트리구조임을 알아채고 tree dp 인것같아서 그쪽으로 생각을 돌렸다.

 

a노드에서 자식노드 b,c,d 가 있을 때 그중 최소값으로 연결하고, 나머지는 더하면 되는데 구현에 대한 아이디어가 부족했다. 탑다운으로 짜려고 했는데 먼가 생각할게 많은 것 같았고, 위상정렬로 풀었다. 

 

지금 생각해보니 위상정렬이랑 dp 바텀업이랑 모양새가 많이 비슷한 것 같다. 

 

#include <bits/stdc++.h>
using namespace std;
#define MAX 200005
#define pii pair<int, int>
#define ll long long
#define pll pair<ll, ll>
#define INF 1e9
#define LINF 1e18
#define all(v) (v).begin(), (v).end()

int indegree[MAX];
ll num[MAX];
ll par[MAX];
vector<ll> adj[MAX];
int n;

void solve(){
    ll ans = 0;
    queue<int> q;
    for(int i=1; i<=n; i++){
        if(indegree[i]==0)q.push(i);
    }
    while(!q.empty()){
        int a = q.front();
        if(a==0){
            for(auto val : adj[a]) ans+=val;
            cout << ans << '\n';
            return;
        }
        q.pop();
        ll min_v = LINF;
        if(adj[a].size()==0)min_v = 0;
        for(auto val : adj[a]){
            ans += val;
            min_v = min(min_v, val);
        }
        ans -= min_v;
        indegree[par[a]]--;
        adj[par[a]].emplace_back(max(min_v, num[a]));
        if(indegree[par[a]]==0)q.push(par[a]);
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int T = 1;
    cin >> T;
    int zzz = 1;
    while(T--) {
        cout << "Case #" << zzz++ << ": ";
        cin >> n;
        for(int i=1; i<=n; i++)cin >> num[i];
        for(int i=0; i<=n; i++)adj[i].clear();
        for(int i=1; i<=n; i++){
            int a;
            cin >> a;
            par[i] = a;
            indegree[a]++;
        }
        solve();
        for(int i=1; i<=n; i++)indegree[i] = 0;
    }
}