백준 2056[자바] java

문제 링크: https://www.acmicpc.net/problem/2056

2056번: 작업

▶문제

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

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

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

---

▶입력

첫째 줄에 N이 주어진다.

두 번째 줄부터 N+1번째 줄까지 N개의 줄이 주어진다. 2번째 줄은 1번 작업, 3번째 줄은 2번 작업,..., N+1번째 줄은 N번 작업을 각각 나타낸다. 각 줄의 처음에는, 해당 작업에 걸리는 시간이 먼저 주어지고, 그다음에 그 작업에 대해 선행 관계에 있는 작업들의 개수(0 ≤ 개수 ≤ 100)가 주어진다. 그리고 선행 관계에 있는 작업들의 번호가 주어진다.

---

▶출력

첫째 줄에 모든 작업을 완료하기 위한 최소 시간을 출력한다.

---

▶해설

문제를 접했을 때 선행 작업이라는 단어만 보고, 위상정렬로 풀려고 해 봤습니다. 하지만 동시에 작업하는 경우 시간의 오래 걸리는 것만 체크하므로 풀 수 없었습니다.(물론 다른 분들은 풀 수도 있습니다..)

 

그래서 DP로 접근했습니다.

 

선행 작업이 없다면 바로 수행을 합니다. 

하지만 선행 작업이 있는 경우 그것을 수행하고 할 수 있습니다.  

 

1. 선행 작업이 없다면, 주어진 시간 그대로 수행됩니다.

2. 선행 작업이 있다면, 선행 작업을 끝낸 시간 + 지금 작업의 시간을 구합니다..

 

따라서 점화식이 아래와 같이 세워집니다. 

dp[i] = Math.max(dp[i], dp[Integer.parseInt(s2[j+2])]+arr[i]);

선행 작업 + 현재 작업이 걸리는 시간의 최댓값을 구합니다. 

 

그 후 가장 큰 값을 추력해주면 해결됩니다. 

전체 코드

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

public class Main {

    static int n;
    static List<Integer>[] lists;
    static int [] arr;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());

        arr = new int[n+1];
        int [] dp = new int[n+1];

        String[] s = br.readLine().split(" ");

        dp[1] = Integer.parseInt(s[0]);

        for(int i=2; i<=n; i++){
            String[] s2 = br.readLine().split(" ");
            arr[i] = Integer.parseInt(s2[0]);
            dp[i] = arr[i];
            for(int j=0; j<Integer.parseInt(s2[1]); j++){
                dp[i] = Math.max(dp[i], dp[Integer.parseInt(s2[j+2])]+arr[i]);
            }
        }

        OptionalInt result = Arrays.stream(dp).max();

        System.out.println(result.getAsInt());

    }
}