시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 1024 MB | 243 | 59 | 45 | 29.605% |
$N$개의 작업을 병렬처리하는 프로그램을 개발하였다. $N$개의 작업을 실행 시간이 다 다르고, 모든 작업에는 순서가 존재한다.
하나의 작업의 실행이 끝나면 다음 작업들에 신호를 준다. 신호를 받은 작업의 실행 조건은 이전 작업들로 부터 신호를 다 받았을 때만 실행할 수 있다.
위 그림과 같이 작업 $A$, $B$, $C$, $D$, $E$가 있고 작업의 순서가 정해져있다. 맨 처음에 작업 $A$을 실행하여 작업 $E$까지 실행한다. 이때, 작업 $A$와 같이 맨 처음에 시작해야하는 작업과 작업 $E$와 같이 맨 마지막으로 실행되는 작업은 반드시 하나가 존재한다.
작업 $A$부터 작업 $E$까지 실행 시간은 순서대로 1초, 2초, 3초, 2초, 1초라고 가정하자. 5개의 작업들이 실행되는 순서는 다음과 같다.
따라서, 작업 $E$가 5초 후에 실행 종료된다.
그런데 해당 프로그램에서 맨 처음에 시작해야하는 작업과 맨 마지막으로 실행되는 작업을 제외한 나머지 $N-2$개의 작업 중 정확히 $K$개를 실행 시간을 0초로 강제로 바꿔도 프로그램에 아무런 문제가 발생하지 않는다는 것을 확인했다.
정확히 $K$개의 작업의 실행시간을 강제로 0초로 바꾸었을 때 모든 작업이 완료되는 데에 최소 시간을 구하시오.
작업의 개수 $N$개, 작업 순서를 알려주는 개수 $M$, 실행 시간을 강제로 0초로 바꿀 수 있는 작업 개수 $K$가 공백으로 구분되어 주어진다. 이때, 작업 순서는 하나의 작업이 끝난 이후 어떤 작업이 실행되는지 알려주는 정보이다.
2번째 줄에는 $N$개 작업에 대한 실행 시간이 공백으로 구분되어 주어진다.
3번째 줄부터 $M + 2$줄까지 작업 순서에 대한 정보가 들어온다. 각 정보는 두 개의 정수 $S$, $E$가 공백으로 구분되어 주어지며, 작업 $S$가 끝난 후 작업 $E$가 실행된다는 의미이다.
작업의 시작 번호는 항상 1이고 이 작업으로 모든 작업이 실행되는 것을 보장한다.
작업 $A$, $B$, $C$가 있다고 했을 때, 작업의 순서가 $A \rightarrow B \rightarrow C \rightarrow A$와 같이 사이클을 이루는 경우가 없는 것을 보장한다.
정확히 $K$개 작업의 실행 시간을 0초로 바꿨을 때, 모든 작업이 완료되는 데에 걸리는 최소 시간을 출력한다.
5 6 1 1 2 3 2 1 1 2 1 3 1 4 2 5 3 5 4 5
4
실행 시간이 3초인 3번 작업을 0초로 바꾸면 된다.
5 6 0 1 2 3 2 1 1 2 1 3 1 4 2 5 3 5 4 5
5