https://www.acmicpc.net/problem/2056
2056번: 작업
수행해야 할 작업 N개 (3 ≤ N ≤ 10000)가 있다. 각각의 작업마다 걸리는 시간(1 ≤ 시간 ≤ 100)이 정수로 주어진다. 몇몇 작업들 사이에는 선행 관계라는 게 있어서, 어떤 작업을 수행하기 위해
www.acmicpc.net
위상정렬과 동적계획법으로 접근가능한 문제다.
풀이법
처음에는 단순히 위상정렬을 통해 큐에 접근할 때마다 가장 오래 걸린 작업시간들을 더하면 될 것이라 생각했다. 하지만 해당방법은 틀린 방법이 다.
후속이 없는 작업의 경우, 다음 탐색에 영향을 끼치지 않아야 하는데, 처음생각한 방법은 이러한 부분을 제외시키지 못했다. 따라서 해당 작업을 완료하는데 걸리는 총시간을 담은 dp 배열을 생성한 뒤, 동적계획법으로 접근해야 한다. next는 다음 작업, curr는 현재작업을 의미할 때, 점화식은 다음과 같다. 여기서 time배열은 순수 작업시간을 의미한다.
dp[next] = max(dp[next], dp[curr]+time[next])
위상정렬을 통한 그래프탐색 이후, dp배열의 최댓값을 출력하면 된다.
정답 코드
'Problem Solving > BOJ' 카테고리의 다른 글
| [1504] 특정한 최단 경로 (0) | 2023.01.04 |
|---|---|
| [1238] 파티 (0) | 2023.01.04 |
| [14567] 선수과목 (0) | 2023.01.01 |
| [1584] 게임 (0) | 2022.12.30 |
| [25587] 배수로 (0) | 2022.12.29 |