새소식

인기 검색어

Algorithm/Python

[백준]1202 보석도둑 (우선순위 큐) - Python

  • -

 

 

1202번: 보석 도둑

첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci

www.acmicpc.net

 

 

  • N, K가 주어짐
  • N줄에 걸쳐 보석의 정보(무게 M, 가격 V)가 주어짐
  • K줄에 걸쳐 가방의 크기 (= 넣을 수 있는 보석의 최대 무게)가 주어짐
  • 각 가방에는 보석을 최대 1개만 넣을 수 있음
  • 상덕이가 훔칠 수 있는 보석의 최대 가격을 구하라

 

  • 가치가 큰 보석을 최대한 크기가 작은 가방에 넣어줌
    (가치가 큰 보석을 크기가 작은 가방부터 순회하며 넣을 수 있다면 넣고 방문처리)
  • 가방이 다 찼다면 최대 보석가치를 가져온 것임

입력 후 정렬 상태

이 풀이 방식으로는 시간초과를 피할 수 없었다.
문제 해결을 위해 다른 블로그와 유튜브를 찾아보다 우선순위 큐라는 개념을 학습했다.

 

 

 

import sys
imput = sys.stdin.readline

n, k = map(int, input().split())
# 보석과 가방 입력
jem = [list(map(int, input().split())) for _ in range(n)]
bag = [int(input()) for _ in range(k)]
# 보석을 무게순으로 정렬한 후 가치가 높은순으로 다시정렬
jem = sorted(jem, key=lambda x:x[0])
jem = sorted(jem, key=lambda x:x[1], reverse=True)
# 가방은 크기가 작은거부터 정렬
bag = sorted(bag)

pack = [False]  # 가방을 사용했는지 체크
ans, cnt = 0, 0     # 보석의 가치, 사용한 가방 개수
for i in range(len(jem)):
    for j in range(len(bag)):
        # 정렬된 보석을 돌면서 작은 가방부터 확인
        # 가방이 비어있고, 보석이 가방에 들어갈 수 있는 크기라면
        if jem[i][0] <= bag[j] and pack[j] == False:
            pack[j] == True     # 가방 사용했다고 체크
            ans += jem[i][1]    # 보석 가치 더해줌
            cnt += 1            # 가방 사용개수 +1
            break
    # 가방을 전부 사용했다면 반복종료
    if cnt == len(bag):
        print(ans)
        break

 

 

  • FIFO 구조인 일반적인 큐와 달리 데이터에 우선순위를 부여해 들어간 순서에 상관없이 우선 순위가 높은 데이터가 먼저 나오는 구조이다.
  • 힙(Heap)이라는 완전이진트리 자료구조를 가지고 구현한다.
  • 보석과 가방을 무게, 크기기준 오름차순 정렬
  • 가방의 길이만큼 반복하며 현재 가방에 들어갈 수 있는 만큼만
    최대 힙을 이용해 우선순위 큐에 저장
  • 반복 1회가 끝나면 우선순위 큐에서 가장 우선순위가 높은 보석을 꺼냄

보석, 가방 정렬

1번째 가방 반복,                                2번째 가방 반복

보석 리스트에서 현재 가방에 들어갈 수 있는 보석들을
보석 크기순으로 우선순위를 부여해 우선순위 큐에 넣은 상태

 

import sys
import heapq
input = sys.stdin.readline

n,k = map(int,input().split())
gem = [list(map(int,input().split())) for _ in range(n)]
bag = [int(input()) for _ in range(k)]
gem.sort()  # 보석을 무게순 정렬
bag.sort()  # 가방 크기순 정렬

Q =[]   # 우선순위 큐가 될 리스트
answer = 0
# 가방 작은 순부터 반복
for i in bag:
    # 보석의 무게가 가방에 들어갈수 없을때까지 반복
    while gem and gem[0][0]<=i:
        # 최대힙을 이용해서 우선순위 큐에 추가
        heapq.heappush(Q, -heapq.heappop(gem)[1])
    # 반복이 끝난 후 가장 큐의 앞에있는 값을 pop하여 더해줌
    if Q: answer -= heapq.heappop(Q)
print(answer)

 

 

'Algorithm > Python' 카테고리의 다른 글

[백준]5427 불 (BFS) - Python  (0) 2023.03.30
[백준] 13549 숨바꼭질3 (BFS) - Python  (0) 2023.03.28
[백준] 2573 빙산(BFS) - Python  (0) 2023.03.27
[백준] 1107 리모컨 - Python  (0) 2023.03.14
[백준] 2638 치즈 (BFS) - Python  (0) 2023.03.04
Contents

포스팅 주소를 복사했습니다

이 글이 도움이 되었다면 공감 부탁드립니다.