백준 5896 효율적으로 소 사기

작성일 | In |

메리 크리스마스

문제 링크

알고리즘

  • 자료 구조
  • 우선순위 큐
  • 그리디

풀이

처음엔 그냥 쿠폰을 썼을 때 가격이 싼 것부터 사버렸다. 하지만 이런 단순한 논리는 먹히지 않았다.

질문 게시판을 읽고 그저 모든 가능한 가격 중 가장 싼 것을 고른다고 최선의 선택이 아니라는 걸 깨달았다. 가장 싼 쪽에 쿠폰을 써버리면 더 비싼 경우에서 큰 할인을 놓칠 수 있다고 한다.

제시된 반례는 다음과 같다.

2 1 6
10 4
2 1

answer: 2


그래서 다음과 같은 논리로 문제를 풀어가기로 했다.

  1. 먼저 쿠폰을 사용했을 때 가장 가격이 싼 소부터 산다.
  2. 쿠폰이 더 이상 없다면, 남은 소들은 그냥 정가에 살지 혹은 이전에 썼던 쿠폰을 물리고 쿠폰을 지금의 소를 사는 데에 사용할지 결정한다.

따라서 만약에 쿠폰을 다 소모한 상황이라도, 나머지 소를 살 때 이전에 쿠폰으로 산 소를 쿠폰 없이 그냥 사고 현재 소를 쿠폰을 사용해서 사는 비용이 더 이득인 경우를 파악해야 한다.


전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
import heapq
import sys
input = sys.stdin.readline

n, k, m = map(int, input().split())

lst = []
for i in range(n):
    p, c = map(int, input().split())
    lst.append((p, c))
    
lst.sort(key = lambda x : (x[1], x[0]))

paid = 0
count = 0

heap = []

for i in range(k):
    if lst[i][1] + paid <= m:
        paid += lst[i][1]
        count += 1
        heapq.heappush(heap, lst[i][0] - lst[i][1])
        
for i in range(k, n):
    if heap and heap[0] + lst[i][1] < lst[i][0]: # 쿠폰을 물렸으니 추가되는 비용 + 남은 소의 할인 가격 < 남은 손의 정가
        if paid + heap[0] + lst[i][1] <= m:
            paid += heapq.heappop(heap) + lst[i][1]
            count += 1
            heapq.heappush(heap, lst[i][0] - lst[i][1])
            
    else:
        if paid + lst[i][0] <= m:
            paid += lst[i][0]
            count += 1
            
print(count)