[Baekjoon] 1202. 보석 도둑

2025. 1. 28. 00:19·코딩테스트/Python
728x90
반응형

🔗 Problem Link

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


❔Thinking

  • 보석의 무게와 가격이 주어질 때, 가방에 보석 하나씩만을 담아 최대 가격을 반환한다.

💻Solution

import heapq
import sys
input = sys.stdin.readline

N, K = map(int, input().split())
jewels = []
bags = []

for _ in range(N):
    weight, value = map(int, input().split())
    jewels.append((weight, value))

for _ in range(K):
    bags.append(int(input()))

jewels.sort() 
bags.sort()

max_heap = []
total_value = 0
j = 0

# 가방을 하나씩 처리
for bag in bags:
    # 현재 가방에 넣을 수 있는 모든 보석을 힙에 추가
    while j < N and jewels[j][0] <= bag:
        heapq.heappush(max_heap, -jewels[j][1])
        j += 1

    if max_heap:
        total_value += -heapq.heappop(max_heap)

print(total_value)

🗝️keypoint

  1. 해당 가방에 담을 수 있는 모든 보석 가운데에서 가장 높은 가격의 보석을 하나씩 담아 나간다.
  2. 현재 가방의 무게까지 가능한 모든 보석을 담고, 가장 높은 가격을 반환하는 heapq를 만들어 push와 pop을 반복한다.
저작자표시 (새창열림)

'코딩테스트 > Python' 카테고리의 다른 글

[Baekjoon] 1025. 제곱수 찾기  (1) 2025.01.30
[Programmers] Level 2. 혼자 놀기의 달인  (0) 2025.01.28
[Programmers] Level 2. 혼자서 하는 틱택토  (0) 2025.01.24
[Baekjoon] 2493. 탑  (0) 2025.01.20
[Programmers] Level 2. 요격 시스템  (0) 2025.01.18
'코딩테스트/Python' 카테고리의 다른 글
  • [Baekjoon] 1025. 제곱수 찾기
  • [Programmers] Level 2. 혼자 놀기의 달인
  • [Programmers] Level 2. 혼자서 하는 틱택토
  • [Baekjoon] 2493. 탑
swwho
swwho
일상을 데이터화하다
  • swwho
    하루한장
    swwho
  • 전체
    오늘
    어제
    • 분류 전체보기 (188)
      • ML_DL (39)
        • MUJAKJUNG (무작정 시리즈) (18)
        • 딥러닝 공부하기 (21)
      • 데이터사이언스 (1)
        • EDA (1)
        • 데이터과학을 위한 통계 (0)
      • 데이터엔지니어링 (2)
      • 논문리뷰 (2)
        • Computer Vision (2)
      • Python 활용하기 (12)
      • 코딩테스트 (127)
        • Python (109)
        • MySQL (14)
      • Git (3)
      • MySQL 활용하기 (0)
      • 일상 이야기 (1)
  • 블로그 메뉴

    • 홈
    • 태그
  • 최근 글

  • 250x250
  • hELLO· Designed By정상우.v4.10.3
swwho
[Baekjoon] 1202. 보석 도둑
상단으로

티스토리툴바