Time Limit: 1s
Memory Limit: 128MB
대학원생 n명이 함께 일을 하려고 한다. 선행작업이 있는 경우, 모든 선행작업이 완료된 이후에 진행할 수 있다.
최대한 빨리 한다면 며칠만에 끝마칠 수 있을지 구해보자. 단, 이들은 대학원생이므로 휴일은 주어지지 않는다.
* Line 1: 사람수 n이 입력된다. (1≤n≤10)
* Line 2: 작업의 갯수 N이 입력된다. (1≤N≤50)
* Line 3~N+2: 작업 0부터 작업 N-1까지 작업 소요날짜 d, 필요인원 p, 선행작업 갯수s와 번호 si가 입력된다. (1≤d≤10, 1≤p≤n, 0≤s≤N-1, 0≤si≤N-1)
* Line 1 : 최소 소요기간을 출력한다.
3 6 1 1 0 2 1 1 3 2 1 0 1 1 0 1 2 3 0 1 2 4 1 0
4
1명이 4일간 작업 5를 하고, 나머지 2명이 작업 0~4를 진행하면 4일 안에 가능하다.
가능한 답은 여러 가지 있으며, 그 중 하나는 다음과 같다.
위상정렬을 공부해보자.
| 사람0 | 사람1 | 사람2 | |
|---|---|---|---|
| 1일 | 작업0 | 작업3 | 작업5 |
| 2일 | 작업1 | 작업2 | 작업5 |
| 3일 | 작업1 | 작업2 | 작업5 |
| 4일 | 작업4 | 작업4 | 작업5 |