# [소프티어] 금고털이

[Softeer - 현대자동차그룹 SW인재확보플랫폼](https://softeer.ai/practice/6288)

이 문제 같은 경우는 그냥 직관적으로 풀어도 통과하기도 한다 (실행 때 마다의 미세한 시간 차이 때문에)

Naive Sol

```javascript
import sys

w, n = map(int, input().split())

golds = []

for i in range(n):
    golds.append(list(map(int, input().split())))

golds.sort(key=lambda x: -x[1])

gram = 0
answer = 0
for i in golds:
    if gram >= w:
        break
    if gram + i[0] <= w:
        gram += i[0]
        answer += i[0] * i[1]
    else:
        temp = w - gram
        gram = w
        answer += temp * i[1]

print(answer)
    
```

하지만 우리는 최대부터 고려하면 되기 때문에, 그때의 최대만을 계속 뽑아낼 수 있는 heap을 쓸 수 있다

Sol

```javascript
import heapq

w, n = map(int, input().split())

# 1g당 금 가격의 역순으로 최대 힙 구성
golds = []
for _ in range(n):
    weight, price = map(int, input().split())
    heapq.heappush(golds, (-price, weight))

gram = 0
answer = 0

while golds and gram < w:
    neg_price, weight = heapq.heappop(golds)
    price = -neg_price  # 원래의 가격 복원

    if gram + weight <= w:
        gram += weight
        answer += weight * price
    else:
        remaining = w - gram
        answer += remaining * price
        break

print(answer)

```

For the site tree, see the [root Markdown](https://slashpage.com/all-about-tika.md).