BOJ_1202 : 보석 도둑

김진현·2021년 5월 22일

BOJ

목록 보기

14/33

출처 : https://www.acmicpc.net/problem/1202

문제

세계적인 도둑 상덕이는 보석점을 털기로 결심했다.

상덕이가 털 보석점에는 보석이 총 N개 있다. 각 보석은 무게 Mi와 가격 Vi를 가지고 있다. 상덕이는 가방을 K개 가지고 있고, 각 가방에 담을 수 있는 최대 무게는 Ci이다. 가방에는 최대 한 개의 보석만 넣을 수 있다.

상덕이가 훔칠 수 있는 보석의 최대 가격을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000)

다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000)

다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci ≤ 100,000,000)

모든 숫자는 양의 정수이다.

출력

첫째 줄에 상덕이가 훔칠 수 있는 보석 가격의 합의 최댓값을 출력한다.

아이디어

가장 큰 가치의 보석을 가장 작은 용량의 가방에 넣는다.

코드

Mine (시간 초과)

import sys

input = lambda : sys.stdin.readline()

#N, K
N, K = map(int, input().split())

#jew 정의
jew = [list(map(int, input().split())) for _ in range(N)]

#bag 정의
bag = [int(input())for _ in range(K)]

#main
bag.sort() # 작은 무게의 가방부터 검사
heap = []
tot = 0 # 보석 가격의 총합
for i in range(K):
    for j in range(N):
        if jew[j][0] <= bag[i]:
            if temp[1] < jew[j][1]:
                temp[0], temp[1] = j, jew[j][1]
    jew[temp[0]] = [0,0] #가방에 넣은 보석 정보 0,0으로 초기화
    tot += temp[1]
    temp = [0,0] #temp 초기화
print(tot)

Clone

# 최대힙을 구현하기 위해 heapq 모듈 import
import sys, heapq
n, k = map(int,sys.stdin.readline().split())
gem_list = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]

# temp : 최대힙을 만들어 주기 위해 빈 리스트 생성
temp = []
ans = 0

# 가방 입력
for i in range(k):
    a = int(sys.stdin.readline())
    # [가방의 무게, 가방의 가치] : 가방은 보석들과 구분 되기 위해 보석의 최대 가치보다 더 크게
    # 설정하거나 -1로 설정함으로서 해당 원소가 가방임을 알려준다
    gem_list.append([a,2000000])

# 무게 순 정렬
gem_list.sort()

for i in gem_list:
    # 가방이 아니라면 보석이므로 최대 힙에 담는다
    if i[1] != 2000000:
        # heapq는 최소힙이므로 넣을 때 -1을 곱해 최대힙으로 변형시킨다
        # 자세한 설명은 heapq 모듈을 검색하는것을 추천한다
        heapq.heappush(temp, (-1 * i[1], i[1]))
    else:
        # 만일 가방의 갯수가 보석보다 많다면 pop할 수 없으므로 예외처리
        try:
            ans += heapq.heappop(temp)[1]
        except:
            pass
print(ans)