인기도:C(A,B,C), 성공률:보통(낮음,보통,높음), 레벨:3(1~4)

맥(Mack)이라는 이름의 거북이가 여틀(Yertle)왕의 거북이 왕좌(王座)을 만들기 위한 거북이를 쌓는 방법을 문의해왔다. 혹시 자기 등껍질이 깨질까 봐 겁이 났기 때문이다. 여틀 왕의 왕좌을 만들기 위해 동원된 5,607마리의 거북이는 체중과 체력이 모두 다르다. 가능한 가장 많은 거북이를 쌓는 방법을 찾아보자.

여러 줄이 입력되는데, 한 줄에 한 쌍의 정수가 입력된다. 첫번째 정수는 체중을, 두번째 정수는 거북이의 체력을 나타낸다. 거북이의 체중은 그램 단위로 입력된다. 즉 체중이 300g이고 체력이 1,000g인 거북이등 위에는 700g을 올려놓을 수 있다. 거북이는 최대 5,607마리이다.

어떤 거북이도 자기 체력이 허용하는 한도 내에서만 등 위에 다른 거북이를 올려놓으면서, 몇 마리의 거북이를 쌓을 수 있는지를 나타내는 정수를 출력한다.

~cpp 
300 1000
1000 1200
200 600
100 101

500 700
200 400
1100 1300
5400 7900
10 20
1 10
700 9000
100 200

10000 60000
20000 70000
9000 59000
600 90000
900 7000
800 800

~cpp 
3

6

6

작성자	사용언어	개발시간	코드
신재동	Python	52분	WeightsAndMeasures/신재동
황재선	Python	2시간+?	WeightsAndMeasures/황재선
문보창	C++	.	WeightsAndMeasures/문보창
김상섭	C++	3시간	WeightsAndMeasures/김상섭

테스트가 너무 적은 듯. 풀기는 풀었는데 체점하려니 python은 지원하지 않아 확인 못함...=,= 나중에 C++로 변경해서 해봐야겠음. --재동
번역을 왜 저렇게 했나요? -- 보창
헉! 내가 학원에서 읽은 동화책 내용이다 --세환
배경설명 - Yertle이라는 거북이 왕이 더 멀리 내려다 보려고(자신이 내려다 보는것들을 자신이 지배하고 있다고 생각함) 왕좌, 한마디로 앉을 곳을 만드는데 거북이들을 쌓아서 만드는것이다. 처음엔 10마리 정도로 시작하다가 욕심이 끝이 없어서 계속 계속 거북이들을 쌓는다. Mack은 맨 밑에 깔려있던 거북이 이름.

예전에 올렸던 풀이가 왜 틀렸는지 한번쯤 생각해 보았으면 좋겠다. Greedy한 방식이 항상 최적해를 찾지 않는다는 사실을 반례를 들어 간단히 보일 수도 있다. 그렇다면 올바른 풀이를 한번 찾아봅시다. -- 보창
----
문제분류