작업 완료 최소 시간
면접 대비시간 제한2초메모리 제한256 MB
각 작업의 기간과 선행 작업 관계(선행 작업 번호는 항상 더 작음)가 주어질 때, DP로 최장 경로를 계산해 모든 작업을 마치는 최소 시간을 구합니다.
문제
수행해야 할 작업이 N개 있다. 3 <= N <= 10000이며, 각 작업의 수행 시간은 1 이상 100 이하의 정수이다.
어떤 작업은 시작하기 전에 반드시 끝나야 하는 선행 작업이 있다. K번 작업의 선행 작업 번호는 모두 1 이상 K - 1 이하이다. 선행 작업이 없는 작업이 하나 이상 존재하며, 1번 작업은 항상 선행 작업이 없다.
서로 선행 관계가 없는 작업들은 동시에 수행할 수 있다. 모든 작업을 끝내는 데 필요한 최소 시간을 구하라.
입력
첫째 줄에 작업의 개수 N이 주어진다.
둘째 줄부터 N개의 줄에 걸쳐 1번 작업부터 N번 작업까지의 정보가 순서대로 주어진다. 각 줄에는 먼저 해당 작업의 수행 시간이 주어지고, 이어서 선행 작업의 개수 C(0 <= C <= 100)가 주어진다. 그 뒤에는 선행 작업 C개의 번호가 주어진다.
출력
모든 작업을 완료하는 데 필요한 최소 시간을 한 줄에 출력한다.
힌트
한 작업의 완료 시간은 그 작업의 수행 시간에 모든 선행 작업 중 가장 늦게 끝나는 작업의 완료 시간을 더한 값이다. 전체 완료 시간은 각 작업의 완료 시간 중 최댓값이다.