😎 문제

#1202 보석도둑

🐶 처음 든 생각

단순하게 생각했을떄
가장 높은 가치를 가진 보석을 배낭에 집어넣되,
무게가 들어가는 순서대로 큰 배낭에 집어넣으면 될듯.

knapsack인가?

근데 이거 그거 아닌가 그 컴수2에서 배운 배낭에 뭐 집어넣기
..사실 기억나는게 비둘기랑 배낭밖에 없음🕊

검색하니까 knapsack problem 아닌가 했는데,
이 경우랑은 다른것 같다.
여기선 가방 하나에는 딱 하나의 보석만 담을 수 있다는 조건이라서, 그렇게 복잡하게 접근하지 않아도 될듯.

🕊처음 짠 코드

import sys

input = sys.stdin.readline
N, K = map(int, input().split())

jewels = []
for _ in range(N):
    x, y = map(int, input().split())
    jewels.append((x, y))
jewels = sorted(jewels, key=lambda x: -x[1]) # 무게 기준으로 정렬

visited_jewels = [False] * N # 방문한 보석 체크

backpacks = []
for _ in range(K):
    backpacks.append(int(input()))
backpacks = sorted(backpacks) # 가장 큰 것부터 정렬
visited_backpacks = [False] * K # 보석 넣은 배낭 체크

res = 0
for i in range(len(backpacks)):
    for k in range(len(jewels)):
        if jewels[k][0] <= backpacks[i] and not visited_backpacks[i] and not visited_jewels[k]:
            res += jewels[k][1]
            visited_jewels[k] = True
            visited_backpacks[i] = True

print(res)

오.. 시간초과....