Algorithm/Baekjoon

[Algorithm]Baekjoon 14267번 : 회사 문화 1

MaxLevel 2023. 11. 17. 13:20

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

 

14267번: 회사 문화 1

영선회사에는 매우 좋은 문화가 있는데, 바로 상사가 직속 부하를 칭찬하면 그 부하가 부하의 직속 부하를 연쇄적으로 칭찬하는 내리 칭찬이 있다. 즉, 상사가 한 직속 부하를 칭찬하면 그 부하

www.acmicpc.net

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
 
int n, m, a, b;
vector<vector<int>> graph(100001);
int nums[100001] = { 0 };
int answers[100001] = { 0 };
 
 
void DFS(int node, int sum)
{
    for (int i = 0; i < graph[node].size(); ++i)
    {
        int nextNode = graph[node][i];
 
        answers[nextNode] = sum + nums[nextNode];
        DFS(nextNode, sum + nums[nextNode]);
    }
}
 
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> n >> m;
 
    for (int i = 1; i <= n; ++i)
    {
        cin >> a;
 
        if (i == 1) continue;
        graph[a].push_back(i);
    }
 
    for (int i = 0; i < m; ++i)
    {
        cin >> a >> b;
        nums[a] += b;
    }
 
    DFS(1, 0);
    
    for (int i = 1; i <= n; ++i)
    {
        cout << answers[i] << ' ';
    }
}
 
 cs

 

어렵지 않은 문제이다. 유의해야할 것은, 칭찬은 여러번 받을 수 있다는 것이다.

이런 설명이 안되어있는게 아쉽고, 테스트케이스에라도 표현해놨으면 좋을 것 같다.