우유생산팀 선발 > 문제은행

본문 바로가기


문제은행

1032 : 우유생산팀 선발

제한시간: 1000 ms    메모리제한: 32 MB
해결횟수: 5 회    시도횟수: 14 회   



농부 영호의 N(1≤N≤500)마리의 소들은 세계적으로 유명한 Multistate Milking Match-up(MMM) 대회에 참가할 우유생산 팀을 선발하려고 한다. 아마 당신도 알고 있듯이 최소한 X(1≤X≤1,000,000) 갤런의 우유를 생산한 어떤 팀도 승자가 된다.

 

각각의 소는 -10,000 부터 10,000 갤런 사이의 기여를 할 수 있는 잠재력을 가지고 있다. (슬프게도 몇몇의 소들은 다른 소들이 생산한 우유가 담긴 우유병을 엎어버리기도 한다.)

 

MMM 대회는 가족의 가치를 촉진 시킨다는데 스스로를 자랑스러워 한다. 농부 영호의 소들은 X 갤런의 우유를 생산해서 승자가 될 것에는 전혀 의심치 않는다. 하지만 대회의 정신을 지지하기 위해 그들은 가능한 많은 부모-자식 관계들을 포함한 팀을 출전시키려고 한다(여전히 최소 X갤런의 우유를 생산하면서). 놀랄것도 없이 농부 영호의 모든 소들은 암컷이다.

 

농부 영호의 소들의 가족 계보도와 각각의 소들이 우유 생산에 기여하는 양이 주어졌을 때 영호가 선택할 수 있는 승자 팀중에 가능한 부모-자식 관계의 수의 최대값을 계산하라. 할머니-어머니-딸 조합의 소들 집합은 두 개의 부모-자식 관계가 있다(할머니-어머니 어머니-딸).


첫 번째줄에 공백으로 구분된 두 개의 정수 N과 X가 주어진다. 두 번째줄 ~ N+1번째 줄까지 공백으로 구분된 2개의 정수로 구성된다. 첫 번째 수는 이 소가 기여하게 될 우유의 갤런 수이다. 두 번째 수는 (1..N 범위의) 이 소의 '어머니'의 번호이다. 만약 소의 어머니가 알려져 있지 않다면 이 숫자는 0이 된다. 가족 정보에는 싸이클이 없다: 어떤 소도 그녀 자신의 어머니 혹은 할머니 등이 될 수 없다.



가능한 승자 팀 중에 가장 많은 부모-자식 관계를 가지는 그 수를 출력한다.

만약 어떤 팀도 승자가 될 수 없으면 -1을 출력한다.


[Copy]
5 8
-1 0
3 1
5 1
-3 3
2 0
[Copy]
2





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