문제
N개의 작업이 있고, 각 작업은 특정 선행 작업들이 모두 끝난 뒤에야 시작할 수 있다. 각 작업마다 소요 시간이 주어질 때, 모든 작업을 마치는 최소 시간을 구한다. 선행 작업 번호는 항상 현재 작업 번호보다 작음이 보장된다.
입력
- 첫째 줄: 작업 수 N (3 이상 10,000 이하)
- 이후 N개의 줄: 작업 소요 시간 T, 선행 작업 수 P, 선행 작업 번호 P개
출력
- 모든 작업을 마치는 최소 시간
예제
| 입력 | 출력 |
|---|---|
7 5 0 1 1 1 3 1 1 6 1 2 1 2 2 4 8 2 3 5 4 1 7 | 23 |
풀이
선행 작업 번호가 항상 현재 번호보다 작음이 보장되므로 입력 순서 자체가 위상 정렬 순서이다. 이를 활용해 DP로 각 작업의 최소 시작 시간을 계산한다.
dp[i]를 "작업 i가 끝나는 최소 시간"으로 정의한다.- 각 작업 i에 대해 소요 시간
t와 선행 작업 목록을 읽는다. dp[i] = t로 초기화한다.- 각 선행 작업 j에 대해
dp[i] = max(dp[i], t + dp[j])로 갱신한다. - 모든
dp[i]중 최댓값이 답이다.
핵심 아이디어: 선행 작업 번호가 항상 더 작다는 조건이 DAG(방향 비순환 그래프)의 위상 정렬 순서를 보장한다. 따라서 별도의 위상 정렬 없이 입력 순서대로 DP를 진행하면 된다. 각 작업의 완료 시간은 "자신의 소요 시간 + 선행 작업들 중 가장 늦게 끝나는 시간"이다.
코드
package com.ssafy.an.day099;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Day81BOJ2056작업DFS { // 2056 작업 - DFS 방법
static int N, ans;
static int[] dp;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = null;
N = Integer.parseInt(br.readLine());
ans = 0;
dp = new int[N];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
int t = Integer.parseInt(st.nextToken()); // k번째 작업에 걸리는 시간
int p = Integer.parseInt(st.nextToken()); // 선행되는 parent 수
dp[i] = t;
for (int j = 0; j < p; j++)
dp[i] = Math.max(dp[i], t + dp[Integer.parseInt(st.nextToken()) - 1]);
ans = Math.max(ans, dp[i]);
}
System.out.println(ans);
br.close();
}
}복잡도
- 시간: O(N + E) — N개의 작업과 E개의 선행 관계 처리 (E는 총 선행 작업 수)
- 공간: O(N) — dp 배열 크기