금고털이

풀이

전형적인 냅색 알고리즘 문제다. 그 중에서도 그리디로 접근 가능한 fraction knapsack이다.

최대 가치를 항상 먼저 뽑아줘야 하는 게 포인트이므로 내림차순 정렬으로 풀었는데 시간 초과가 발생했다.

그래서 최대힙을 이용하여 최대 가치를 뽑아주었다.

코드

정렬 (시간 초과)

import sys
input = sys.stdin.readline

def greedy_knapsack(w,m_list):
    max_price = 0
    m_list.sort(reverse=True)
    for p,m in m_list:
        if w >= m:
            max_price += m*p
            w -= m
        else:
            max_price += w*p
            break
    return max_price

w,n = map(int,input().split())
m_list = list()
for _ in range(n):
    m,p = map(int,input().split())
    m_list.append((p,m))
max_price = greedy_knapsack(w,m_list)
print(max_price)

힙 (정답)

import sys
import heapq as h
input = sys.stdin.readline

def greedy_knapsack(w,m_list):
    max_price = 0
    while m_list:
        p,m = h.heappop(m_list)
        p *= -1
        if w >= m:
            max_price += m*p
            w -= m
        else:
            max_price += w*p
            break
    return max_price

w,n = map(int,input().split())
m_list = list()
for _ in range(n):
    m,p = map(int,input().split())
    h.heappush(m_list,(-p,m))
max_price = greedy_knapsack(w,m_list)
print(max_price)