시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 128 MB | 2172 | 0 | 0 | 0.000% |
어떤 회사의 작업 공정은 아래에서 위로(bottom-up) 진행된다. 즉, 말단 사원들이 우선 처음 부분을 진행하고, 작업이 완료되면 그 상사가 작업물을 전달받아 다음 작업을 진행하고, 다시 그 위의 상사가 작업을 마저 진행하는 방식이다. 이러한 작업 공정을 정리하면 다음과 같다.
이러한 작업 공정을 이용하여 이 회사에서는 작업을 진행하고 있었다. 하지만 경기가 나빠지면서 사장은 일부 직원을 해고하기로 결심하였다. 직원을 해고한 후의 빈 자리는 다른 직원을 이용하여 대체하기로 하였다. 즉, 말단 직원들의 경우에는 자신의 작업을 완료한 후에는 할 일이 없게 되는데, 이때 다른 상사의 작업을 이 직원들이 진행하면 좀 더 적은 수의 직원으로도 작업을 진행할 수 있다. 반대로 말단 직원들을 해고한 후에 사장 등의 상사들이 그 작업을 진행할 수도 있다. 단, 직원들을 해고한 후에도 작업의 효율이 떨어지지 않아야 한다. 즉, 모든 직원이 있었을 때 보다 전체 작업이 완료되는 시간이 늘어나서는 안 된다.
각 직원들의 관계가 주어졌을 때, 전체 작업 완료 시간을 유지하면서 해고할 수 있는 직원의 최대 수를 구하는 프로그램을 작성하시오.
첫째 줄에 직원의 수를 나타내는 정수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 차례로 1번, 2번, …, N번 직원의 직속 상사의 번호가 주어진다. 사장의 경우에는 -1이 주어진다.
첫째 줄에 전체 직원들이 있을 때 필요한 최소 작업 완료 시간을 출력한다. 둘째 줄에 해고할 수 있는 직원의 최대 수를 출력한다.
7 -1 1 1 2 2 3 3
3 3