[BOJ] 14267. 회사 문화1 (🥇, 트리 DP)

🔗

풀이

모든 부하들은 한 명의 직속 상사를 갖게 된다. 트리 형태로 나타낼 수 있다.

2번이 2의 정도를 갖는 칭찬을 받게 되면 그 아래에 있는 3, 4, 5가 모두 칭찬의 수치에 +2를 하게 된다는 것이다. 매번 dfs를 돌려서 리프 노드까지 탐색해서 더해주면 되겠지만 트리의 구조를 생각해봤을 때 굳이 그럴 필요는 없다.

우선 각 직원들은 한 명의 상사만을 갖게 되고, 각 상사들은 자신이 얻은 칭찬의 수치가 존재한다. 1은 상사가 없기 때문에 건너뛰고 2는 자신이 직접 얻은 칭찬의 수치 2에 1로부터 받게 되는 칭찬의 수치 0을 더한 값을 갖게 된다. 3은 자신이 얻은 칭찬의 수치 4에 마찬가지로 상사가 얻은 칭찬의 수치를 얻게 되는데 이때 상사는 2만 고려하면 된다. 물론 1의 칭찬의 수치가 3에게도 내려오기 때문에 3은 1의 칭찬의 수치도 가져와야 하지만 그 부분은 이미 2가 자신의 직접 적인 상사인 1의 칭찬의 수치를 가져오는 과정으로부터 계산이 되었기 때문에 3은 자신의 직접 상사인 2의 칭찬의 수치만 가져오면 된다. 오히려 여기서 1의 칭찬의 수치를 가져오면 값이 중복된다.

결국 모든 직원들은 자신의 직속 상사가 가지고 있는 칭찬의 수치 값만 가져와서 더해주면 된다. 이 모든 과정은 dfs 를 하지 않고 1차원 배열을 만들어 dp로 풀 수 있는데, 이유는 직속 상사의 번호는 자신의 번호보다 작으며, 최종적으로 1번이 사장이다 라는 조건이 존재하기 때문이다. 상사들이 더 작은 번호를 갖기 때문에 1부터 n까지 순서대로 조회하면 항상 상사의 칭찬 수치 들이 먼저 계산되어 있기 때문에 풀이가 가능하다

출력 방식

0 2 6 6 12

해당 형태로 출력했어야 하는데 처음엔 하나씩 출력하고 뒤에 " "를 붙였었다.

StringBuilder 생성해서 하나의 문자열로 만들고 출력하니까 시간이 절반으로 줄었다.

StringBuilder sb = new StringBuilder();

for (int i = 1; i < n+1; i++) {
   sb.append(degree[i]).append(" ");
}
System.out.println(sb);

최종 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
import java.util.stream.Stream;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        
        int n = Integer.parseInt(st.nextToken());
        int m  = Integer.parseInt(st.nextToken());
        int[] parent = new int[n+1]; // 부모 노드
        int[] degree = new int[n+1]; // 칭찬의 정도
        
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i < n+1; i++) {
            parent[i] = Integer.parseInt(st.nextToken());    
        }

        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int p = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());
            degree[p] += w;
        }
        
        int par;
        for (int i = 2; i < n+1; i++) {
            par = parent[i];
            degree[i] += degree[par];
        }

        StringBuilder sb = new StringBuilder();

        for (int i = 1; i < n+1; i++) {
            sb.append(degree[i]).append(" ");
        }
        System.out.println(sb);
    }
}