계보 > 문제은행



문제은행

1181 : 계보

제한시간: 1000 ms    메모리제한: 128 MB
해결횟수: 3 회    시도횟수: 6 회   



외계인 태구는 자기 가족의 족보를 알고자 한다. 몇주를 열심히 조사해서 그는 트리 형태의 가계도의 베타 버전을 제작할 수 있게 되었다. 불행하게도, 몇 명의 조상은 매우 많은 부모를 가지고 있는 것으로 조사가 되었기에 완성된 가계도는 "잘된 형태"를 이루지 못하고 있었다("좋은 형태"란 가계도 내에서 각각의 에일리언이 한번만 나타나고, d개보다 많은 부모를 가지고 있지 않을 경우 이를 "좋은 형태"라고 한다. 참고로, 한 외계인은 d명의 부모를 가질 수 있다).

그리고 태구는 조금 더 조사를 해본 결과 몇 개의 조사된 부모-자식 관계는 조상-후예의 관계일 것이라고 추측을 하게 되었으며, 따라서 몇 개의 선조를 추가시켜서 "좋은 형태"를 이루고자 한다. 너무 많은 선조를 추가시킬 경우 가계도가 인위적이 되어버리기 때문에, 태구는 "좋은 형태"를 이루기 위해서 추가시켜야 하는 조상의 최소 개수를 알고자 한다.

예를 들어, d=2일 경우 베타 버전의 가계도는 다음과 같이 조사되었다고 하자.

e3050b66a1b29a01767400d7560a4131_1449741
 

위의 경우는 "좋은 형태"가 아니지만, 아래와 같이 2개의 조상을 추가 시키면 다음과 같이 "좋은 형태"의 가계도가 만들어 진다.

e3050b66a1b29a01767400d7560a4131_1449741
 




베타 버전 가계도 내에서 태구의 조상은 1번부터 n번의 번호가 붙어서 구분 된다(태구의 번호는 0번이다.)
첫 번째 줄에는 조상의 개수 n과 d가 주어진다(2≤n≤100,000, 2≤d≤n).
그 다음 줄에는 n개의 숫자가 주어지는데, I번째의 숫자는 I번째 외계인의 자식의 번호가 주어진다.




입력된 가계도를 "잘된 형태"로 만들기 위해서 추가해야하는 조상의 개수를 출력하라.



6 2
5 5 0 5 0 5
2



HancomEducation E-mail : hancomc@hotmail.com, comkiwer@naver.com Tel : 031-388-0999 FAX : 031-388-0996 정올소개 이용약관 개인정보처리방침
경기도 안양시 동안구 호계동 1065-10 협성골드프라자 601호, 경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호
Copyright@2010-2015 jungol. All right reserved.