[백준] BOJ 14267회사 문화 1(골드 4)

문제

---

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

14267번: 회사 문화 1

---

해설

---

1. 현재 자식의 부모를 입력으로 받으므로, 입력으로 들어온 부모의 인접리스트를 관리한다.
2. 이때, 자식이 있는 경우에만 인접리스트를 생성하고 나중에 인접리스트가 null이면 자식이 없는 경우로 사용한다
   (-> dfs 기저조건)
3. 입력받은 칭찬받은 인원과 칭찬의 값을 배열에 모두 저장한다.
   ex) 2번 칭찬 -> ans[2]에 저장
4. 칭찬이 모두 끝나면 부모 노드부터 dfs탐색을 하며 자식들의 칭찬 값에 더해준다.

---

주의 사항

---

1. 그림에서 3, 4, 5가 중복으로 방문된다.
2. 만약 M개의 칭찬 입력마다 dfs를 돌리면 중복되는 부분이 생겨 시간초과 발생
3. 따라서 기본 로직의 3번 ans[2]에 저장하는 로직을 통해 해당 인원이 받은 칭찬만 일단 저장해둔다.
4. 이후, 루트 노드 (1)에서부터 dfs를 통해 모든 자식에 부모의 칭찬을 더해서 업데이트 해준다

---

코드 (DFS + DP)

---

import java.io.*;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
    static StringBuilder sb = new StringBuilder();
    static ArrayList<Integer>[] arr;
    static long[] ans;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        ans = new long[N + 1];

        arr = new ArrayList[N + 1];
        st = new StringTokenizer(br.readLine());
        st.nextToken();
        for (int i = 2; i <= N; i++) {
            int parent = Integer.parseInt(st.nextToken());
            if(arr[parent] == null) arr[parent] = new ArrayList<Integer>();
            arr[parent].add(i);
        }

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int current = Integer.parseInt(st.nextToken());
            int value = Integer.parseInt(st.nextToken());
            ans[current] += value;
        }
        dfs(1, ans[1]);

        for (int i = 1; i <= N; i++) {
            sb.append(ans[i]).append(" ");
        }
        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }

    private static void dfs(int current, long value) {
        ans[current] = value;
        if(arr[current] == null) return;
        for (int i = 0; i < arr[current].size(); i++) {
            int child = arr[current].get(i);
            dfs(child, value + ans[child]);
        }
    }
}

---

결론

---

문제를 나이브하게 풀었을 때 시간초과가 너무 났다!.

친구에게 시간초과의 힌트를 듣고 해결했던 문제 (중복되는 연산을 메모이제이션 하는 것을 생각해보자!)

---