[백준 C++] 14267번 회사 문화 1

14267번: 회사 문화 1

문제 요약

문제

영선회사에는 매우 좋은 문화가 있는데, 바로 상사가 직속 부하를 칭찬하면 그 부하가 부하의 직속 부하를 연쇄적으로 칭찬하는 내리 칭찬이 있다. 즉, 상사가 한 직속 부하를 칭찬하면 그 부하의 모든 부하들이 칭찬을 받는다. 모든 칭찬에는 칭찬의 정도를 의미하는 수치가 있는데, 이 수치 또한 부하들에게 똑같이 칭찬 받는다. 직속 상사와 직속 부하관계에 대해 주어지고, 칭찬에 대한 정보가 주어질 때, 각자 얼마의 칭찬을 받았는지 출력하시오,

사용 알고리즘

다이나믹 프로그래밍

입출력

• 입력: 첫째 줄에는 회사의 직원 수 n명, 최초의 칭찬의 횟수 m이 주어진다. 직원은 1번부터 n번까지 번호가 매겨져 있다. (2 ≤ n, m ≤ 100,000) 둘째 줄에는 직원 n명의 직속 상사의 번호가 주어진다. 직속 상사의 번호는 자신의 번호보다 작으며, 최종적으로 1번이 사장이다. 1번의 경우, 상사가 없으므로 -1이 입력된다. 다음 m줄에는 직속 상사로부터 칭찬을 받은 직원 번호 i, 칭찬의 수치 w가 주어진다. (2 ≤ i ≤ n, 1 ≤ w ≤ 1,000) 사장은 상사가 없으므로 칭찬을 받지 않는다.
• 출력: 1번부터 n번의 직원까지 칭찬을 받은 정도를 출력하시오. ``` 예제1

입력 5 3 -1 1 2 3 4 2 2 3 4 5 6 출력 0 2 6 6 12

## 풀이
매우 간단한 누적합 문제다.
먼저, 칭찬을 주는 상사와 그 정도를 입력받아 해당 직원에게 직접 칭찬 값을 기록해둔다. 그 후 트리 구조에서 루트(사장)부터 시작해서 자식 노드로 내려가면서, 부모의 칭찬값을 자식에게 더해주는 방식으로 누적합을 구하면 된다.
이 방식은 DFS나 BFS로 트리를 순회하면서 상사의 칭찬을 아래로 전파하는 구조로, 각 직원의 최종 칭찬 점수를 쉽게 계산할 수 있다.

## 어려웠던 점
없다.

## 배운 점 / 느낀 점
없다.

## 전체 코드
```cpp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int n, m;
vector<vector<int>> company;
vector<int> praise;

void dfs(int node, int w){
    praise[node] += w;
    for(int i : company[node]){
        dfs(i, praise[node]);
    }
}

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

    cin >> n >> m;
    company = vector<vector<int>>(n+1, vector<int>());
    praise = vector<int>(n+1, 0);
    int k, kk;
    cin >> k;
    for(int i = 2; i <= n; i++){
        cin >> k;
        company[k].push_back(i);
    }
    for (int i = 0; i < m; i++) {
        cin >> k >> kk;
        praise[k] += kk;
    }
    dfs(1, 0);
    for (int i = 0; i < n; i++) {
        cout << praise[i+1] << ' ';
    }
    return 0;
}