백준 14267번 - 회사 문화 1

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

14267번: 회사 문화 1

 

• 필요한 배경지식

트리에서의 다이나믹 프로그래밍

 

 

 

• 문제 해결 방법

문제를 읽어보면 직원들의 관계가 트리형태로 이루어져 있다는 것은 충분히 확인할 수 있습니다.

또한 i번째 직원이 받은 총 칭찬의 수는 i번째 직원이 직속 상사로부터 받은 칭찬과 i번째 직원을 부하로 가지는 모든 직원들이 직속 상사로부터 받은 칭찬을 더한 값이라고 볼 수 있습니다.

 

예시로 아래와 같은 트리를 살펴 봅시다.

 

상하관계 예시1

 

i번째 직원이 직속 상사로부터 받은 칭찬을 p[i]라고 할때 직원 3, 5, 7, 9 들이 받은 총 칭찬의 양을 예시로 살펴보면

p[3] = p[3] + p[2]

p[5] = p[5]

p[7] = p[7] + p[6]

p[9] = p[9] + p[7] + p[6]

이렇게 총 칭찬의 양을 구할 수 있을 것입니다.

그렇다면 i번째 직원의 직속상사를 모두 배열에 저장하고 직원1이 나올때까지 직원i의 상사를 계속해서 역추적하면 위와 같이 직원i가 받은 총 칭찬의 양을 구해낼 수 있습니다.

 

하지만 이렇게 하나하나 상사들의 칭찬 값을 탐색하여 더하면 시간초과를 피할 수 없습니다.

아래의 트리형태를 살펴 봅시다.

 

상하관계 예시2

 

p[2] = p[2] + p[3] + p[4]

p[3] = p[3] + p[4]

p[4] = p[4]

 

2부터 N까지 차례대로, 직원이 받은 총 칭찬의 수를 모두 구하기 위해서는 위처럼 계속해서 같은 값을 탐색하여 더해야만 합니다. N의 최댓값이 작다면 문제가 되지 않지만 문제에서 N의 최댓값은 100000이므로 100000개의 노드가 위와 같은 트리형태로 이루어져 있다면 시간초과를 피할 수 없습니다.

 

이 문제는 다이나믹 프로그래밍을 이용하여 해결할 수 있습니다.

아래의 코드에서는 탑다운 방식으로 DP를 수행했습니다.

 

 

 

 

• C++ 전체 코드

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

int N,M;
int par[100001]{};
int sum[100001]{};
int dp[100001]{};

// 탑다운 DP
int solve(int n){
    if(n==-1) return 0;
    if(dp[n]!=-1) return dp[n];
    else dp[n] = sum[n];
    return dp[n] += solve(par[n]);
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin>>N>>M;
    int a,b;
    for(int i=1; i<=N; i++){
        cin>>a;
        par[i] = a;
    }
    for(int i=0; i<M; i++){
        cin>>a>>b;
        sum[a] += b;
    }
    
    memset(dp,-1,sizeof(dp));
    for(int i=1; i<=N; i++){
        cout<<solve(i)<<' ';
    }

}