백준 2056 (1) 썸네일형 리스트형 백준 2056 작업 - 위상정렬과 dp가 함께 쓰이는 문제 문제 링크 www.acmicpc.net/problem/2056 2056번: 작업 수행해야 할 작업 N개 (3 ≤ N ≤ 10000)가 있다. 각각의 작업마다 걸리는 시간(1 ≤ 시간 ≤ 100)이 정수로 주어진다. 몇몇 작업들 사이에는 선행 관계라는 게 있어서, 어떤 작업을 수행하기 위해 www.acmicpc.net 풀이 아이디어 작업을 완료하기 위해 어떤 작업이 먼저 수행되어야 하는지를 파악해야 하므로 당연히 위상정렬 문제이다. 친절하게 각 줄의 두번째 int 값으로 indegree(먼저 수행되어야 하는 노드, 즉 조상노드의 개수)가 써져 있으므로 그대로 써먹으면 된다. (numOfancestor) dp는 바로 이 '선행되는 조상노드의 실행 시간의 최댓값' 을 파악하기 위해 사용된다. 쉽게 예를 들어보.. 이전 1 다음