[백준] 1202 보석 도둑

📖 문제

---

🧑🏻‍💻 풀이 과정

1) 문제 이해 및 접근

가방에 담을 수 있는 모든 보석들 중 가장 가치가 높은것을 담으면 최대 가치를 얻을 수 있습니다.

그리디 방식으로 접근하여 풀이했습니다.

2) 알고리즘

• 그리디

3) 풀이 코드

사용 언어 - Python

import sys
import heapq
from collections import deque
sys.stdin = open('input.txt')

N, K = map(int, sys.stdin.readline().split())                                                                   # 보석의 개수, 가방의 개수
gems = deque(sorted([list(map(int, sys.stdin.readline().split())) for _ in range(N)], key=lambda x: x[0]))      # 각 보석의 무게와 가격들을 보석의 무게순으로 오름차순
backpacks = sorted([int(sys.stdin.readline()) for _ in range(K)])                                               # 가방을 가벼운 순서대로 정렬
answer = 0

available = []                                      # 담을 수 있는 보석들
for backpack in backpacks:                          # 가벼운 가방부터 탐색 시작
    while gems and backpack >= gems[0][0]:          # 보석 리스트에 보석이 남아있고, 현재 가방에 들어갈 수 있다면
        heapq.heappush(available, -gems[0][1])      # 보석의 무게를 음수로 하여 저장 (heapq는 최소힙 -> 음수를 저장하여 최대힙으로 활용)
        gems.popleft()                              # 보석 리스트의 가장 앞의 보석을 삭제

    if available:                                   # 담을 수 있는 보석이 있다면
        answer += -heapq.heappop(available)         # 가장 가치가 높은 보석을 가방에 담음


print(answer)

---

📝 결과 및 학습한 내용

1) 어려웠던 내용

보석은 가치순으로 내림차순으로 정렬하여 리스트 생성하였고, 가방은 담을 수 있는 무게순으로 오름차순하여 리스트 생성하였습니다.

이후, 보석을 하나씩 확인하며 보석의 무게와 같거나 큰 가방들을 이분탐색으로 탐색하였고, 정답을 찾는 방식을 이용하였습니다.

 

그러나 위의 과정에서 두개의 리스트의 길이에는 변화가 있지 않고 탐색을 진행하다보니 시간 복잡도가 높아 시간 초과가 발생하였습니다.

 

이후 탐색 시간을 줄이기 위하여 deque 와 최대힙을 이용하여 해결하였습니다.

2) 새롭게 학습한 내용

특별히 없습니다.

---

🔗 문제 링크

- https://www.acmicpc.net/problem/1202

1202번: 보석 도둑

 

 

※ 오류 및 오타, 다른 의견이 있는 경우 댓글을 남겨주시면 감사하겠습니다