문제 출처

1. 문제설명

  • 직원과 그 위의 상사가 있다.
  • 상사 한명이 칭찬하면 연결된 그 밑에 직원은 전부 칭찬 받는다.
  • 각 직원의 칭찬 횟수를 구하라

  • 단 사장은 칭찬하는 사람이 없다.

  • 문제 분류
    • DP, Graph, Tree, DFS, DP in Tree


2. 알고리즘 설계

  • 계급도 == 트리
  • 각 직원의 상사를 저장하고, 직원과 상사의 인접행렬을 표기한다.
  • 칭찬 받은 직원의 수를 카운팅 배열에 저장한다.
    • 참고로 한 명이 여러번 칭찬 받을 수 있으니, =이 아닌 +=으로 해야한다.
    • 이거 때문에 맞왜틀 시전….
  • 이후 자신의 상사가 -1(사장)이 아니면 칭찬 횟수를 더해주고,
  • 연결된 다른 상사를 갱신하는 DFS를 수행한다.


3. 전체 코드

#include <bits/stdc++.h>
using namespace std;

const int SZ = 100'005;
int n, m, u, v;
vector<int> adj[SZ];
int cnt[SZ], P[SZ];

void dfs(int cur) {
    if(P[cur] != -1) cnt[cur] += cnt[P[cur]];
    for(int nxt : adj[cur])
        dfs(nxt);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> m;
    for(int i=1; i<=n; i++) {
        cin >> P[i];
        if(P[i] == -1) continue;
        adj[P[i]].push_back(i);
    }

    while(m--) {
        cin >> u >> v;
        cnt[u] += v;
    }

    dfs(1);

    for(int i=1; i<=n; i++) cout << cnt[i] << ' ';

    return 0;
}


4. 팁

  • 이전부터 쓰던 100'005 표기법이 있다.
  • 우리 나라만 그런지 모르겠지만, 보통 3자리씩 컴마(,)로 숫자를 적는다.
  • C++에서는 ' 표기를 이용한 숫자 표기를 지원한다.
    • 낮은 버전에서는 동작하지 않으니, 주의하자