[백준/JAVA] BOJ 2056 - 작업

오랜만에 위상 정렬을 풀어봤는데요, 제가 싫어하는 dp가 껴 있는 줄은 몰랐네요?

👀 문제

2056번: 작업 ✨ 골드 4

수행해야 할 작업 N개 (3 ≤ N ≤ 10000)가 있다. 각각의 작업마다 걸리는 시간(1 ≤ 시간 ≤ 100)이 정수로 주어진다.

몇몇 작업들 사이에는 선행 관계라는 게 있어서, 어떤 작업을 수행하기 위해 반드시 먼저 완료되어야 할 작업들이 있다. 이 작업들은 번호가 아주 예쁘게 매겨져 있어서, K번 작업에 대해 선행 관계에 있는(즉, K번 작업을 시작하기 전에 반드시 먼저 완료되어야 하는) 작업들의 번호는 모두 1 이상 (K-1) 이하이다. 작업들 중에는, 그것에 대해 선행 관계에 있는 작업이 하나도 없는 작업이 반드시 하나 이상 존재한다. (1번 작업이 항상 그러하다)

모든 작업을 완료하기 위해 필요한 최소 시간을 구하여라. 물론, 서로 선행 관계가 없는 작업들은 동시에 수행 가능하다.

예제 입력

7
5 0
1 1 1
3 1 2
6 1 1
1 2 2 4
8 2 2 4
4 3 3 5 6

예제 출력

23

힌트

• 1번 작업 : 0~5
• 2번 작업 : 5~6
• 3번 작업 : 6~9
• 4번 작업 : 5~11
• 5번 작업 : 11~12
• 6번 작업 : 11~19
• 7번 작업 : 19~23
  
  

🔑 키포인트

위상 정렬 다이나믹 프로그래밍

✍️ 코드

📍 작업들이 동시 수행이 가능하므로, 걸리는 시간을 계산할 때 dp를 이용해 준다
dp[다음 작업] = Math.max(dp[다음 작업], dp[현재 작업] + 다음 작업 수행 시간)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class BOJ2056_작업 {
    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[] chasu = new int[n + 1];
        int[] times = new int[n + 1];
        int[] dp = new int[n + 1];
        ArrayList<ArrayList<Integer>> arr = new ArrayList<>();
        for (int i = 0; i < n + 1; i++) {
            arr.add(new ArrayList<>());
        }

        Queue<Integer> q = new LinkedList<>();
        for (int i = 1; i < n + 1; i++) {
            st = new StringTokenizer(br.readLine());
            times[i] = Integer.parseInt(st.nextToken());
            int cha = Integer.parseInt(st.nextToken());
            chasu[i] = cha;
            if (cha == 0) {
                q.offer(i);
                dp[i] = times[i];
            }
            for (int c = 0; c < cha; c++) {
                int num = Integer.parseInt(st.nextToken());
                arr.get(num).add(i);
            }
        }

        while (!q.isEmpty()) {
            int now = q.poll();
            for (int next : arr.get(now)) {
                dp[next] = Math.max(dp[next], dp[now] + times[next]);
                if (--chasu[next] == 0) {
                    q.offer(next);
                }
            }
        }

        int answer = 0;
        for (int i = 1; i < n + 1; i++) {
            answer = Math.max(answer, dp[i]);
        }
        System.out.println(answer);
    }
}