BOJ 5896 - 효율적으로 소 사기

체감 티어:P3

태그:우선순위 큐, 정렬, 그리디

 

파머 존의 쿠폰을 뺏어가면 되는거 아닌가요

 

---

우선 파머 존에게 k 개의 쿠폰과 돈 m이 있다.

파머 존은 많은 소를 사고 싶어 하므로 최적의 방법으로 소를 살 수 있게 도와주면 된다.

i 번째 소를 구입하려면 원가 Pi 또는 쿠폰 할인가 Ci를 지불해야 한다.

 

1. 쿠폰 할인가가 싼 소부터 쿠폰을 쓰는 것이 좋다

당연한 얘기이다. 하지만 원가를 지불하고 다른 소를 사는 것이 이득일 수 있다.

 

2. 쿠폰을 다른 소에게 쓰는 경우가 있을 수 있다

우리는 이것을 우선순위 큐를 통해 쿠폰을 쓸 필요가 없는 소를 찾을 수 있다!

k 개의 쿠폰을 전부 사용해 쿠폰을 쓸 예정인 소 목록을 만들자.

이제 남은 소들을 보며 현재 Pi 원과 이전의 소를 쿠폰 없이 사고 Ci 원을 지불하는 것이 이득인지 판별하면 된다.

 

---

역시나 그리디의 발상 방식은 참신하고 재밌다.