백준 5896 효율적으로 소 사기

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

5896번: 효율적으로 소 사기

그리디한 접근법을 적용할 수 있는 문제이다. 간단히는 소의 숫자가 i+1인 경우의 최적해에서 고른 소가 i인 경우의 소를 항상 포함하기에 그리디한 접근이 가능하다고 보면 되겠다.

k개의 소를 구매할 때까지는, 쿠폰을 사용한 가격 중 낮은 순서부터 고르는 것이 최적임은 자명하다. 

그 이후에는 2가지 경우가 있는데, 하나는 남은 소들 중 쿠폰을 적용하지 않았을 때 가장 싼 소를 가져가는 것이다. 

또는 쿠폰을 사용하는 소를 추가해야 하는데, 쿠폰을 사용한 소들 중 하나를 쿠폰을 사용하지 않게 바꾸고 쿠폰을 사용하는 소를 추가해야 한다. (바꾸는 소를 고르는건 비용이 최소가 되도록 Priority Queue를 이용하자.)

이렇게 바꾸지 않을 경우, 보고 있는 소를 추가하는 것보다 지금 가지고 있는 소를 유지하면서 위의 경우를 사용하는 것이 낫기 때문이다. 다시 말해, 이미 쿠폰을 사용한 A라는 소가 있다고 하자. 시장에는 A보다 쿠폰가가 낮은 소가 없기에, A를 쿠폰을 사용하던 사용하지 않던 항상 데리고 있는 상태를 유지하는 게 최적이라는 것이다. 

이제 소의 숫자를 늘려 가며 2가지 경우 중 더 사용하는 돈이 적은 걸 선택하면 된다.

(쿠폰을 사용한 소의 가격과 사용하지 않은 소의 가격을 각각 정렬해 두면 시간 내에 해결할 수 있다.)

사용한 돈이 M을 초과하지 않을 때까지 소를 추가하는 걸 반복하면 문제를 해결할 수 있다.