BOJ 13873 - Hotel Rewards

 

여행 갈 때 얼마나 효율적으로 돈을 사용할 수 있는지 생각을 해본 적은 따로 없던 것 같다.

가끔 코딩 문제를 풀다 보면 이런 상황을 자주 마주치게 되는 거 같아 나름? 신선한 거 같기도 하고..

아무튼 이번 문제는 티어에 맞는 난이도를 가지고 있는 것 같다.

 

---

 

문제 요약을 하자면 지내야 하는 호텔들의 수가 주어진다.

각 호텔마다 Pi만큼의 돈을 내야한다.

호텔에 한번 숙박하면 1개의 쿠폰을 주고 k 개의 쿠폰이 모이면 호텔을 한번 무료로 숙박할 수 있다.

이때 사용해야 하는 최소 금액을 출력하는것이 문제가 원하는 것이다.

 

당연히 호텔에 숙박할 때마다 쿠폰 개수가 k보다 크면 사용하는 것이 이득이다.

문제는 이 쿠폰을 어떤 호텔에서 사용하는것이 관건인 것이다.

호텔에 사용할 쿠폰을 정하는것은 최소 힙를 이용해 판별해주면 된다.

i번째 호텔에 쿠폰을 사용했다면 최소 힙에 Pi를 저장한다.

 

쿠폰을 사용한적이 없고 현재 쿠폰의 개수가 k보다 작다면 당연히 그 호텔에서는 돈을 내야한다.

 

만약 쿠폰의 개수가 k보다 크다면 무조건 일단 쿠폰을 사용하는것이 이득일 것이다.

쿠폰을 사용한 호텔에서는 호텔의 가격을 저장한다.

 

쿠폰을 사용한 적이 있고 쿠폰의 개수가 k보다 작으면 우리는 이제 쿠폰을 사용할 호텔을 바꾸는 방법을 선택한다.

Pi를 내는 대신 만약 쿠폰으로 지나간 호텔의 비용이 Pi보다 작다면 현재 호텔에서 쿠폰을 사용하고 쿠폰으로 숙박한 호텔중 가장 비용이 싼 호텔에서 돈을 내는 것으로 바꾼다.