[백준,c++] 14267번 - 회사 문화1

문제

14267번: 회사 문화 1

 

코드

#include <iostream>
#include <vector>

using namespace std;

vector<int>graph[100001];
int point[100001];

void add_point(int node, int _point){
    point[node] += _point;
    for(auto next: graph[node]){
        add_point(next, point[node]);
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int n, m; cin>>n>>m;
    for(int i=1; i<=n; i++){
        int inp; cin>>inp;
        if(inp==-1) continue;
        graph[inp].push_back(i);
    }
    
    for(int i=0; i<m; i++){
        int peo, cost; cin>>peo>>cost;
        point[peo] += cost;  // peo: 직원번호, cost: 칭찬정도
    }
    
    add_point(1, point[1]);
    
    for(int i=1; i<=n; i++){
        cout<<point[i]<<' ';
    }
}

 

풀이

자신이 칭찬받으면 자신보다 아래 직위를 가진 모든 직원의 칭찬 점수 또한 증가시키는 문제입니다.

미리 직원들이 칭찬받은 정도를 입력받고, dfs를 한 번만 돌리면 해결할 수 있습니다. 만약 미리 직원들이 받은 칭찬 정도를 입력받지 않고 입력받을 때마다 dfs를 돌려 점수를 더해준다면 시간 초과가 발생하게 됩니다.

1. 칭찬받은 정도를 먼저 저장한다.
2. dfs를 1번 직원을 시작점으로 수행하는데, 본인이 받은 칭찬 점수를 더한다.
3. 본인 아래의 직원들의 dfs를 돌리는데, 아래의 직원은 본인 상사가 받은 점수를 더한다.