You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
reacted with thumbs up emoji reacted with thumbs down emoji reacted with laugh emoji reacted with hooray emoji reacted with confused emoji reacted with heart emoji reacted with rocket emoji reacted with eyes emoji
Uh oh!
There was an error while loading. Please reload this page.
문제 링크
https://www.acmicpc.net/problem/2056
문제 조건
아이디어
간단한 위상정렬 문제이다.
위상정렬을 진행하면서 선행 작업들에 걸린 시간 중 최댓값에 현재 작업에 걸리는 시간을 더해주면서 작업에 걸리는 시간들을 갱신해나가면 된다.
최종적으로 작업 시간들 중 가장 오래 걸린 시간이 모든 작업을 완료하기 위한 최소 시간이므로 출력해주면 된다.
시간 복잡도
위상정렬에 O(E+V) 시간이 걸린다. 최대 1만개의 정점이 각자 1만개의 간선을 가진다고 해도(실제론 무조건 더 적다) 1억 언저리라서 시간 안 풀이가 가능하다.
구현
All reactions