2056번. 작업

 

아이디어

결국 임의의 i 번째 작업을 가장 빨리 완료할 수 있는 시간은 '선행 작업 중 가장 늦게 끝나는 작업 + i 번째 작업의 소요 시간' 이다.

 

따라서 dp[i] 를 i 번째 작업을 가장 빨리 완수할 수 있는 시간이라고 정의한다면

 

dp[i] = max(dp[선행1], dp[선행2],..) + i 번째 작업의 소요 시간

 

이라고 할 수 있다.

 

그리고 문제에서 요구하는 것은 모든 작업을 완료하기 위한 최소 시간이므로 모든 작업들에 대해 dp[i] 를 구한 뒤 그 중 가장 최대값을 뽑아내면 된다.

 

풀이코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());

        int[] dp = new int[N + 1];
        int result = 0;
        for (int i = 1; i <= N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());

            int time = Integer.parseInt(st.nextToken());
            int cntOfBefore = Integer.parseInt(st.nextToken());


            for (int j = 0; j < cntOfBefore; j++) {
                int before = Integer.parseInt(st.nextToken());
                dp[i] = Math.max(dp[i], dp[before]);
            }

            dp[i] += time;
            result = Math.max(result, dp[i]);
        }

        System.out.println(result);
    }
}