김낭만

재밌거나 필요하다고 생각하는 걸 만듭니다.

백준(BOJ) 1202 보석 도둑 파이썬(Python)

문제 링크

우선순위 큐를 사용하는 그리디 알고리즘 문제.
처음에 그리디 알고리즘인 것 같긴 해서 정렬부터 하고 들어갔는데, 그 다음에 보석을 가치 순으로 넣을 방법을 한참 고민했던 문제.
결국 풀이를 보고 나서야 우선순위 큐를 떠올릴 수 있었다.
풀이만 알면 간단한데, 생각하기가 어려웠던 것 같다.
전술했듯 그리디 알고리즘이므로, 보석과 가방을 무게 오름차순으로 정렬한 이후, 가방에 넣을 수 없을 때까지 보석을 가치를 기준으로 하는 최대 힙에 넣으면 된다.
그 후 더이상 보석을 넣을 수 없게 되면 힙에서 보석을 꺼내 가방으로 옮기면 된다.

from sys import stdin
from heapq import *
input = stdin.readline

n, k = map(int, input().split())
# 입력을 무게 오름차순으로 정렬
gems = sorted([list(map(int, input().split())) for _ in range(n)])
bags = sorted([int(input()) for _ in range(k)])

q = []
g = 0
ans = 0
for bag in bags:
    while g < n and gems[g][0] <= bag:
        # 보석이 남아있는 동안, 그리고 가방의 용량보다 가벼운 동안 힙에 넣기
        heappush(q, (-gems[g][1], gems[g][0]))
        g += 1
    else:
        # 더이상 보석을 넣을 수 없으면 힙에서 보석을 꺼내 넣기
        if not q:
            continue
        ans -= heappop(q)[0]

print(ans)

2024

맨 위로 이동 ↑

2023

세그먼트 트리

개요 선형적인 자료구조에서는 값에 접근하는 데에 \(O(1)\)이면 충분하지만, 대신 부분합을 구하는 데에는 \(O(N)\)이 필요하다. 그렇다면 이 자료구조를 이진 트리로 구성하면 어떨까? 값에 접근하는 데에 걸리는 시간이 \(O(\lg N)\)으로 늘어나지만 대신 부분합을 구하...

벨만-포드 알고리즘

개요 다익스트라 알고리즘과 함께 Single Sourse Shortest Path(SSSP) 문제를 푸는 알고리즘이다. 즉, 한 노드에서 다른 모든 노드로 가는 최단 경로를 구하는 알고리즘이다. 다익스트라 알고리즘보다 느리지만, 음수 가중치 간선이 있어도 작동하며, 음수 가중치 사...

다익스트라 알고리즘

개요 다익스트라 알고리즘은 Single Sourse Shortest Path(SSSP) 문제를 푸는 알고리즘 중 하나이다. 즉, 한 노드에서 다른 모든 노드로 가는 최단 경로를 구하는 알고리즘이다. 단, 다익스트라 알고리즘은 음수 가중치 엣지를 허용하지 않는다. 이 경우에는 벨만-...

맨 위로 이동 ↑