반응형
https://www.acmicpc.net/problem/14267
14267번: 회사 문화 1
영선회사에는 매우 좋은 문화가 있는데, 바로 상사가 직속 부하를 칭찬하면 그 부하가 부하의 직속 부하를 연쇄적으로 칭찬하는 내리 칭찬이 있다. 즉, 상사가 한 직속 부하를 칭찬하면 그 부하
www.acmicpc.net
[ 문제풀이 ]
1. vector<int> arr[ n ]을 만들고, 직속 후배들을 저장합니다.
2. dfs를 활용하여 직속 상사들의 칭찬값들을 모두 더해 후배의 칭찬값에 적용시킵니다.
3. 1부터 n까지 칭찬값을 출력합니다.
[ 소스코드 ]
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 | #include<iostream> #include<vector> using namespace std; vector<int> arr[100001]; int good[100001]; int ans[100001]; int n, m; void dfs(int num, int w) { if (num == 0) return; ans[num] = good[num] + w; for (auto& next : arr[num]) { dfs(next, good[num] + w); } } int main() { scanf("%d %d", &n, &m); for (int i = 1; i <= n; i++) { int parent; scanf("%d", &parent); if (parent != -1) { arr[parent].push_back(i); } } for (int j = 0; j < m; j++) { int i, w; scanf("%d %d", &i, &w); good[i] += w; } dfs(1, 0); for (int i = 1; i <= n; i++) { printf("%d ", ans[i]); } } | cs |
반응형
'백준' 카테고리의 다른 글
| [ 백준 ] 14287번 - 회사 문화 3 (C++) (0) | 2023.05.10 |
|---|---|
| [ 백준 ] 14268번 - 회사 문화 2 (C++) (0) | 2023.05.09 |
| [ 백준 ] 14419번 - Foehn Phenomena (C++) (0) | 2023.05.07 |
| [ 백준 ] 12844번 - XOR (C++) (0) | 2023.05.06 |
| [ 백준 ] 11003번 - 최솟값 찾기 (C++) (0) | 2023.05.05 |