[백준-파이썬] 1202: 보석 도둑

문제 보러 가기!

처음 풀이- 시간 초과 🎇

가방 많이 넣을 수 있는 것부터 하나씩 보면서, 보석을 가격 비싼 순(가격 같으면 무거운 순)으로 봤다. 그 가방에 보석을 넣을 수 있으면, 보석 없애고 가방도 없애고.. 그 가격을 정답에 더했다. 그 가방에 그 보석을 못 넣으면 그냥 보석을 없앴다. (어차피 이후 가방에도 그 보석이 무거워서 못 넣으니까)

예제는 맞기는 한데,, 그랬더니 시간 초과 ㅠ 

코드는 이랬다.

import sys, heapq

input= sys.stdin.readline

N,K = map(int,input().split())
jewelries = []
backpacks = []

for _ in range(N):
    m, v = map(int,input().split())
    jewelries.append((-v, -m)) # 가격 비싼 순으로, 무게 무거운 순으로

for _ in range(K):
    c = int(input())
    backpacks.append(-c) # 용량 큰 순으로

heapq.heapify(jewelries)
heapq.heapify(backpacks)

ans = 0
while backpacks:  # 가방 많이 넣을 수 있는 것부터 보기
    # 가격 비싼 순으로.. 무게 무거운 것부터 보석 보기
    backpack_volumn = backpacks[0]

    while jewelries and backpacks:
        value, weight = jewelries[0]
        if weight >= backpack_volumn:
            ans += (-value)
            heapq.heappop(jewelries) # 보석 사용
            heapq.heappop(backpacks) # 가방 사용
            break
        else:
            heapq.heappop(jewelries) # 그 보석은 그 이후 가방에도 넣을 수 없음.

print(ans)

정답 코드 🎈

1. 보석 무게, 가치를 tuple로 묶어서 리스트에 넣고! 가방 용량도 리스트에 넣는다.
2. 둘 다 오름차순으로 정렬한다.
3. 가방 용량 적은 것부터 보면서(for문), while로 보석들을 쭉 본다.
3-1. 그때 들어갈 수 있는 보석이 나오면, 그 가치를 우선순위 큐에 넣는다.
3-2. 못 넣는 보석이 나오면 안 넣고 break한다.
3-3. 그 가방에 넣을 수 있는 보석 중 가장 가치가 높은 것을 넣는다. (정답에 더해준다.)

가장 값 높은 걸 빼야 하니까 max 우선순위 큐가 필요하다. 그래서 넣을 때, 뺄 때 -1를 곱한다!

import sys, heapq

input= sys.stdin.readline

N,K = map(int,input().split())
jewelries = []
backpacks = []

for _ in range(N):
    m, v = map(int,input().split())
    jewelries.append((m, v))

for _ in range(K):
    c = int(input())
    backpacks.append(c)

jewelries.sort() # 무게 적은 보석부터 오름차순
backpacks.sort() # 용량 적은 가방부터 오름차순

ans = 0
idx = 0
poss = []
for weight in backpacks: # 가방 용량 적은 것부터 보면서
    # 들어갈 수 있는 보석 있나 보기
    while idx < N:
        m, v = jewelries[idx]
        if m <= weight:
            heapq.heappush(poss, -v) # 가방에 들어갈 수 있는 보석
            idx += 1 # 그 다음 보석
        else: # 못 들어가면 그만두기!!(그 다음 보석도 그것보다 무거워서 가방에 못 넣음)
            break

    if poss:
        ans += -heapq.heappop(poss) # 가방에 넣을 수 있는 보석 중 가격 가장 비싼 것을 넣기

print(ans)