[BOJ] 2056 - 작업

개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다.

 

문제

www.acmicpc.net/problem/2056

2056번: 작업

난이도: 골드 4

사용언어: JAVA

 

풀이

이 문제는 다이나믹 프로그래밍을 이용하면 비교적 어렵지 않게 해결할 수 있습니다. 한 작업이 시작되기 전에 완수되어야 할 여러 작업들을 입력으로 받아서, 해당 작업들이 완료되는데 걸리는 시간들을 확인하여 가장 늦게 끝나는 작업의 시간에 자신의 작업 시간을 더해서 dp 배열에 추가해주면 됩니다.

 

t라는 작업 시간을 가지는 i번째 작업을 수행하기 위해서 a와 b라는 작업이 먼저 수행되어야 한다면, 

 

dp[i] = t + max(dp[a], dp[b))

 

라는 식을 세울 수 있습니다.

 

위의 식을 이용해 dp 배열을 채우고, dp 배열 내의 가장 큰 값을 출력해주면 됩니다.

 

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;
 
class Main {
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int N = Integer.parseInt(br.readLine());
        int[] dp = new int[N + 1];
        int i, j;
        int t, n;
        int[] arr = new int[N + 1];
        
        String s;
        StringTokenizer st;
        for (i = 1; i <= N; i++) { // 각 작업 별로 반복문을 실행
            s = br.readLine();
            st = new StringTokenizer(s);
            t = Integer.parseInt(st.nextToken());
            n = Integer.parseInt(st.nextToken());
            for (j = 1; j <= n; j++) { // 먼저 완료되어야 할 작업들의 시간을 arr라는 배열에 저장
                arr[j] = dp[Integer.parseInt(st.nextToken())];
            }
            Arrays.sort(arr, 0, n + 1); // 위에서 만든 배열을 소팅해서
            dp[i] = t + arr[n]; // 가장 큰 값을 작업 시간과 더해서 dp 배열을 채워넣음
        }
        
       Arrays.sort(dp); // dp 배열을 소팅해서
        bw.write(String.valueOf(dp[N])); // 가장 큰 값을 출력
        bw.flush();
    }
}