프로젝트가 끝나는 가장 빠른 시각
- 메모리 제한
- 256 MB
- 정확성 시간 제한
- 10000 ms
- 푼 사람
- 0
어떤 프로젝트는 0번부터 N - 1번까지 N개의 작업으로 이루어져 있고, i번 작업은 하는 데 durations[i]일이 걸립니다.
prereqs[j] = [a, b]는 a번 작업이 끝나야 b번 작업을 시작할 수 있다는 뜻입니다.
일할 사람은 충분히 많아서, 앞선 작업이 모두 끝난 작업은 곧바로 시작할 수 있고 여러 작업을 동시에 진행할 수 있습니다.
프로젝트는 시각 0에 시작합니다. 모든 작업이 끝나는 가장 빠른 시각을 반환하세요.
선후 관계에 순환은 없습니다.
입출력 예
| durations | prereqs | result |
|---|---|---|
[3, 2, 4, 1] | [[0, 2], [1, 2], [2, 3]] | 8 |
[5, 1, 1, 1] | [[1, 2], [2, 3]] | 5 |
[2, 2, 2] | [] | 2 |
입출력 예 설명
예 1 — 0번과 1번 작업을 동시에 시작합니다. 2번 작업은 둘 다 끝나는 시각 3에 시작해 7에 끝나고, 3번 작업이 8에 끝납니다.
예 2 — 1 → 2 → 3은 시각 3에 끝나지만, 0번 작업이 5일 걸립니다.
예 3 — 선후 관계가 없으므로 세 작업을 모두 동시에 진행합니다.
효율성
이 문제에는 효율성 테스트가 있습니다. 제한 사항의 입력 크기를 보고 필요한 시간 복잡도를 직접 판단하세요.
함수 시그니처
solution(durations: int[], prereqs: int[][]) → long
제한 사항
-
durations.length,durations[i] -
prereqs.length,a,b,ab - 같은 선후 관계가 여러 번 주어질 수 있습니다. 선후 관계에는 순환이 없습니다.
- 답은 32비트 정수를 넘을 수 있습니다.
기대 복잡도
- 시간
- O(N + M)
- 공간
- O(N + M)
입출력 예
| durations | prereqs | 기대 출력 |
|---|---|---|
[3,2,4,1] | [[0,2],[1,2],[2,3]] | 8 |
[5,1,1,1] | [[1,2],[2,3]] | 5 |
[2,2,2] | [] | 2 |
힌트
힌트
finish[v]를 "v번 작업이 끝나는 가장 빠른 시각"이라고 하면
입니다. 답은 모든 finish[v] 중 최댓값, 즉 가중치가 있는 DAG에서 가장 긴 경로입니다.
finish[u]가 모두 정해진 뒤에 finish[v]를 계산해야 하므로 위상 정렬 순서로 처리하세요.
진입 차수가 0인 작업부터 큐에 넣고, 꺼낼 때마다 다음 작업들의 시작 가능 시각을 갱신하며 진입 차수를 줄입니다.
복잡도 목표
모든 선후 관계를 값이 더 이상 바뀌지 않을 때까지 반복해서 훑는 풀이는 최악의 경우 이라 효율성 테스트에서 시간 초과가 납니다. 이 필요합니다.
언어별 시간 제한
| 언어 | 효율성 시간 제한 | |
|---|---|---|
| C (GCC, gnu17) | 200 ms | 추정 |
| C++ (GCC, gnu++23) | 200 ms | 도출됨 |
| Python 3.13 | 1000 ms | 도출됨 |
| Java 25 | 1646 ms | 도출됨 |
| Kotlin 2.4 (JVM) | 1400 ms | 추정 |
| C# 14 (.NET 10) | 1400 ms | 추정 |
테스트 그룹
| 그룹 | 배점 | 테스트 수 | 공개 범위 |
|---|---|---|---|
| sample | 0 | 3 | 입력·출력 공개 |
| correctness | 40 | 11 | 판정만 |
| performance | 60 | 4 | 판정만 |