Funcia
Lv.3dagdpgraphtopological-sort

프로젝트가 끝나는 가장 빠른 시각

메모리 제한
256 MB
정확성 시간 제한
10000 ms
푼 사람
0
0

어떤 프로젝트는 0번부터 N - 1번까지 N개의 작업으로 이루어져 있고, i번 작업은 하는 데 durations[i]일이 걸립니다. prereqs[j] = [a, b]는 a번 작업이 끝나야 b번 작업을 시작할 수 있다는 뜻입니다.

일할 사람은 충분히 많아서, 앞선 작업이 모두 끝난 작업은 곧바로 시작할 수 있고 여러 작업을 동시에 진행할 수 있습니다. 프로젝트는 시각 0에 시작합니다. 모든 작업이 끝나는 가장 빠른 시각을 반환하세요.

선후 관계에 순환은 없습니다.

입출력 예

durationsprereqsresult
[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

제한 사항

  • 1≤N=1 \le N = durations.length ≤200,000\le 200{,}000, 1≤1 \le durations[i] ≤10,000\le 10{,}000
  • 0≤M=0 \le M = prereqs.length ≤200,000\le 200{,}000, 0≤0 \le a, b <N< N, a ≠\ne b
  • 같은 선후 관계가 여러 번 주어질 수 있습니다. 선후 관계에는 순환이 없습니다.
  • 답은 32비트 정수를 넘을 수 있습니다.

기대 복잡도

시간
O(N + M)
공간
O(N + M)

입출력 예

durationsprereqs기대 출력
[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]=durations[v]+max⁡(u→v)finish[u](앞선 작업이 없으면 0)\text{finish}[v] = \text{durations}[v] + \max_{(u \to v)} \text{finish}[u] \quad (\text{앞선 작업이 없으면 } 0)

입니다. 답은 모든 finish[v] 중 최댓값, 즉 가중치가 있는 DAG에서 가장 긴 경로입니다.

finish[u]가 모두 정해진 뒤에 finish[v]를 계산해야 하므로 위상 정렬 순서로 처리하세요. 진입 차수가 0인 작업부터 큐에 넣고, 꺼낼 때마다 다음 작업들의 시작 가능 시각을 갱신하며 진입 차수를 줄입니다.

복잡도 목표

모든 선후 관계를 값이 더 이상 바뀌지 않을 때까지 반복해서 훑는 풀이는 최악의 경우 O(N⋅M)O(N \cdot M)이라 효율성 테스트에서 시간 초과가 납니다. O(N+M)O(N + M)이 필요합니다.

언어별 시간 제한

언어효율성 시간 제한
C (GCC, gnu17)200 ms추정
C++ (GCC, gnu++23)200 ms도출됨
Python 3.131000 ms도출됨
Java 251646 ms도출됨
Kotlin 2.4 (JVM)1400 ms추정
C# 14 (.NET 10)1400 ms추정

테스트 그룹

그룹배점테스트 수공개 범위
sample03입력·출력 공개
correctness4011판정만
performance604판정만
에디터 불러오는 중…

아직 결과가 없습니다. 실행 또는 제출하세요.