문제 원문


https://www.acmicpc.net/problem/9869


내 코드




내가 생각한 풀이는 데드라인의 오름차순으로 정렬 한 뒤, 데드라인이 같으면 얻을 수 있는 우유량의 내림차순으로 정렬하는 풀이임.


일단 데드라인이 차이나는 소1, 소2 가 있다고 하면, 데드라인이 빠른 애부터 착유하면 무적권 둘다 짤 수 있음. 1초 밖에 차이가 안 나더라도 바로 다음에 짜면 둘다 짤 수 있음. 그니까 데드라인 오름차순으로 정렬해놓는게 이득.


반면 데드라인이 똑같은 소는 둘다 짤 수 있는 방법이 없으니 어쩔 수 없이 우유량이 가장 많은 놈을 택해야 함. 그러니 데드라인이 같다면 우유 내림차순으로 정렬해놓는게 이득


바로 틀렸습니다 뜨길래 usaco 홈피에서 테케 확인해봤는데


10

4 4

2 1

2 8

1 2

10 5

10 3

9 5

10 1

3 7

8 4


이 케이스 정답이 52거든. 근데 내 건 44가 나와.

[(10, 1), (2, 1), (1, 2), (10, 3), (8, 4), (4, 4), (10, 5), (9, 5), (3, 7), (2, 8)]

내 방식으로 정렬하면 cows 리스트는 이렇고 고르는 과정 출력해보면

time: 0 selected: cows[0](10, 1) current milk: 10
time: 1 selected: cows[2](1, 2) current milk: 11
time: 2 selected: cows[3](10, 3) current milk: 21
time: 3 selected: cows[4](8, 4) current milk: 29
time: 4 selected: cows[6](10, 5) current milk: 39
time: 5 selected: cows[8](3, 7) current milk: 42
time: 6 selected: cows[9](2, 8) current milk: 44


이렇게 되어서 결국 6마리 짜고 44원 얻는게 내 답인데


아무리 봐도 이게 최선인데 어떻게 해야 52원이 나오는건지 몰겠음