[BOJ] 14267번 회사 문화 1

Sol1) 트리 DP

상사가 직속 부하를 칭찬하면 그 부하가 부하의 직속 부하를 연쇄적으로 칭찬하는 내리 칭찬이 있다. 그래프로 간선을 연결해주면 간단하게 트리 DP를 이용해먹을 수 있겠다고 생각했다.

    for (int i = 0; i < trees[cur].size(); i++){
        int next = trees[cur][i];
        if (!visited[next]){
            dp[next] += dp[cur];
            dfs(next);
        }
    }

DFS를 돌기 전에 반영을 해줘야 계속해서 자식 노드에 전달할 수 있다.

 

소스 코드

#include <bits/stdc++.h>
#define FASTIO ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;

#define ll long long
const int MAXN = 100005;
ll dp[MAXN], arr[MAXN];
vector<int> trees[MAXN];
bool visited[MAXN];

void dfs(int cur){
    visited[cur] = true;
    dp[cur] += arr[cur];
    
    for (int i = 0; i < trees[cur].size(); i++){
        int next = trees[cur][i];
        if (!visited[next]){
            dp[next] += dp[cur];
            dfs(next);
        }
    }
}

int main(){
    FASTIO;
    
    int n, m, num, start;
    cin >> n >> m;
    for (int i = 1; i <= n; i++){
        cin >> num;
        if (num == -1) start = i;
        else trees[num].push_back(i);
    }
    for (int i = 0; i < m; i++){
        int a, b;
        cin >> a >> b;
        arr[a] += b;
    }
    
    dfs(start);
    for (int i = 1; i <= n; i++)
        cout << dp[i] << ' ';
    return 0;
}

Sol2) 순차 DP

문제에 " 직속 상사의 번호는 자신의 번호보다 작으며, 최종적으로 1번이 사장이다."라는 말이 있다. 순차적으로 처리한다면 직속 상사가 나보다 먼저 칭찬을 받게 된다는 것이다. 이를 이용하면 한 번에 풀 수 있다.

    for (int i = 2; i <= n; i++){
        if (parent[i] != -1){
            arr[i] += arr[parent[i]];
        }
    }

 

소스 코드

#include <bits/stdc++.h>
#define FASTIO ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;

#define ll long long
const int MAXN = 100005;
int parent[MAXN], arr[MAXN];

int main(){
    FASTIO;
    
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> parent[i];
    for (int i = 0; i < m; i++){
        int a, b;
        cin >> a >> b;
        arr[a] += b;
    }
    
    for (int i = 2; i <= n; i++){
        if (parent[i] != -1){
            arr[i] += arr[parent[i]];
        }
    }
    for (int i = 1; i <= n; i++) cout << arr[i] << ' ';
    return 0;
}

 

같은 부하가 칭찬을 여러 번 받는다는 생각을 못했는지 처음에 cin >> arr[i]를 해버려서 틀렸다.