3621번 - 족보 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 64 MB | 243 | 88 | 77 | 37.745% |
문제
외계인 피터는 그의 족보를 추적하려고 한다. 피터는 몇 주동안 열심히 작업해 족보의 베타 버젼을 만들었다.
족보를 살펴보니 선조 중 일부가 너무 많은 부모를 가졌다는 사실을 알게되었다. (외계인 d명의 부모를 가진다) 그래서 피터는 몇몇 부모-자식 관계는 선조-자손 관계일 것이라고 생각했다.
피터가 족보를 만족스러운 형태로 바꾸려면 최소 몇 명을 추가해야 하는지 구하는 프로그램을 작성하시오.
각각의 외계인의 부모의 수가 d명을 넘지 않고, 각 외계인이 족보에 한 번만 노출된 경우에 만족스러운 형태라고 한다.
예를 들어, d가 2이고 피터가 만든 족보의 베타 버젼이 아래와 같다면,
아래와 같이 선조 두 명을 추가하면 만족스러운 형태가 된다.
입력
첫째 줄에 두 정수 n과 d가 주어진다. (2 ≤ n ≤ 100,000, 2 ≤ d ≤ n) 다음 줄에는 총 n개의 정수가 주어지며, i번째 정수는 i번째 자식의 번호이다.
피터의 족보에 등장하는 선조는 모두 1번부터 n번까지 번호로 나타낸다. 피터의 번호는 0번이다.
출력
족보를 만족스러운 형태로 바꾸기 위해서 최소 몇 명을 추가하면 되는지 출력한다.
예제 입력 1
6 2 5 5 0 5 0 5
예제 출력 1
2
출처
ICPC > Regionals > Northern Eurasia > North-Western Russia Regional Contest > NEERC Northern Subregional 2006 G번
- 문제를 번역한 사람: originerd
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호