[백준 2068번]

이 문제는 dp로 풀었다. dp로 풀 수 있는 이유는 문제에서 다음과 같은 지문때문에 적용이 가능하다. "K번 작업에 대해 선행 관계에 있는(즉, K번 작업을 시작하기 전에 반드시 먼저 완료되어야 하는) 작업들의 번호는 모두 1 이상 (K-1) 이하이다." .

 

선행으로 이루어져야 하는 작업들 중에서 (선행해야하는 작업을 수행하는데에 걸리는 시간 + 현재 작업을 수행하는데에 걸리는 시간) 의 최댓값으로 dp를 갱신하면 된다.

 

import java.io.*;
import java.util.*;

public class solution_for_2056 {
    static int N;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());

        List<List<Integer>> list = new ArrayList<>();
        for (int n = 0; n < N; n++) {
            list.add(new LinkedList<>());
        }

        int[] dp = new int[N+1];
        for (int i = 0; i < N+1; i++) {
            dp[i] = -1;
        }
        
        int[] times = new int[N+1]; // 작업을 수행하는데 걸리는 시간

        for (int n = 1; n < N+1; n++) {
            st = new StringTokenizer(br.readLine());

            int time, jobCnt;

            time = Integer.parseInt(st.nextToken());
            jobCnt = Integer.parseInt(st.nextToken());

            int spentTime = time;
            for (int j = 0; j < jobCnt; j++) {
                int jobNum = Integer.parseInt(st.nextToken());

                spentTime = Math.max(spentTime, dp[jobNum] + time);
            }

            dp[n] = spentTime;
        }

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