[파이썬] 현대자동차 Softeer :: 금고털이 풀이

https://softeer.ai/practice/info.do?idx=1&eid=395

1. 문제

루팡은 배낭을 하나 메고 은행금고에 들어왔다. 금고 안에는 값비싼 금, 은, 백금 등의 귀금속 덩어리가 잔뜩 들어있다. 배낭은 W ㎏까지 담을 수 있다.

 

각 금속의 무게와 무게당 가격이 주어졌을 때 배낭을 채울 수 있는 가장 값비싼 가격은 얼마인가?

 

루팡은 전동톱을 가지고 있으며 귀금속은 톱으로 자르면 잘려진 부분의 무게만큼 가치를 가진다.

 

2. 제약조건

1 ≤ N ≤ 106인 정수

1 ≤ W ≤ 104인 정수

1 ≤ Mi, Pi ≤ 104인 정수

 

3. 입력

첫 번째 줄에 배낭의 무게 W와 귀금속의 종류 N이 주어진다. i + 1 (1 ≤ i ≤ N)번째 줄에는 i번째 금속의 무게 Mi와 무게당 가격 Pi가 주어진다.

 

4. 출력

첫 번째 줄에 배낭에 담을 수 있는 가장 비싼 가격을 출력하라.

 

---

 

5. 풀이

나는 처음에 이 문제를 보고 백준 평범한 배낭 문제가 떠올라서 동적계획법(다이나믹 프로그래밍)을 사용해서 풀어야겠다고 생각했는데, 하다보니 점화식이 생각이 안나서 자연스럽게 그리디 방식 (그리디 알고리즘)으로 풀게 되었다.

 

import sys
from queue import PriorityQueue
W, N = map(int, sys.stdin.readline().split(' '))

q = PriorityQueue(maxsize=N)

for _ in range(N):
    w, v = list(map(int, sys.stdin.readline().split(' ')))
    q.put([-v, w]) # 우선순위 큐에 넣을 때 '가치'를 기준으로 내림차순 정렬함.

def cal():
    sum = 0
    count = 0

    for i in range(N):
        cur_weight = 0
        value, weight = q.get()
        value = (-value)    # '가치' 음수 -> 양수
        # print(weight, value)

        while cur_weight < weight:
            # (탈출 조건) 계산 횟수가 총 중량과 높거나 같으면 현재 가치 리턴.
            if count >= W:
                return sum

            count += 1
            cur_weight += 1
            sum += value

    return sum

print(cal())

 

일단 문제를 보면 배낭을 채울 수 있는 가장 값비싼 가격을 구해야 하므로 1kg당 가치가 제일 높은 물건부터 차례대로 넣어줘야한다는 걸 알 수 있다.

 

그래서 나는 우선순위 큐를 사용해서 가치를 우선순위로 두고 내림차순 정렬을 시킨 다음에 가치가 높은 물건부터 차례대로 넣으면서 가치의 최대합을 구하도록 구현했다.