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/1005
문제 조건
아이디어
정답의 최대치
정답의 최대치를 생각해보면 모든 건물 순서가 1개씩 나열되어 있는 경우이다.
ex) 1 -> 2 -> 3 -> ... -> N
최대 1000개의 건물이 각 10만의 딜레이가 걸린다고 하면 최대 1억이므로 int 자료형으로 충분하다.
접근) 각 건물을 완성하는 시간은?
각 건물은 건설 순서가 존재하고, 이전 건물들이 반드시 지어져 있어야 다음 순서의 건물을 지을 수 있다. 즉, 특정 건물을 짓는데에 걸리는 시간이 T[X]라고 할 때, X의 선행 작업들의 T값을 먼저 계산해야 T[X]의 값을 구할 수 있을 것이다.
따라서 T 배열을 위상 정렬 순서로 시간을 계산해나가면 된다. 이 때 선행 건물들이 반드시 지어져야 하므로
T[X] = max(T[X의 선행 건물]) + D[X]이다.시간 복잡도
단순한 위상정렬 문제로 O(V+E)의 시간이 걸린다. V와 E의 최댓값은 각 1000, 10만 이므로 시간 안 풀이가 가능하다.
구현
All reactions