[#19638] 센티와 마법의 뿅망치

RookieAND·2022년 7월 5일

백준 우선순위큐 코테

BaekJoon

목록 보기

24/42

❓ Question

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

📖 Before Start

우선 순위 큐를 사용하여 가장 작은 수를 추출해야 하는 문제.

이번 문제는 우선순위 큐와 힙 자료구조을 사용하여 풀어야 하는 문제였다.
우선순위 큐와 관련된 문제를 찾던 중, 그나마 만만해보여서 (...) 선택하였다.

✒️ Design Algorithm

키가 큰 거인을 꺼내 키를 확인하고, 이것이 센티보다 작은지를 파악해야 한다.

N 명의 거인들의 키를 대상으로 센티가 T 번만큼의 뿅망치질을 진행한다.
뿅망치에 맞은 거인은 키의 절반을 잃고, 키가 1일 경우 더 이상 줄지 않는다.

결국 이는 거인의 키가 담긴 List 를 우선순위 큐를 통해 최댓값부터 뽑아야 한다.
따라서 다음과 같은 로직을 통해 문제를 풀어나갈 수 있을거라 기대하였다.

N 개의 자연수가 담긴 우선순위 큐에서, 가장 값이 큰 거인의 키를 뽑는다.
이후 해당 값이 센티의 키보다 작은지를 판별하고, 값이 1 인지도 판별한다.
판별이 끝났다면, 거인의 키를 절반으로 줄인 후 이를 다시 힙에 넣는다.
위 작업을 T 회 반복한 후, 우선순위 큐 내에서 가장 큰 거인의 키를 뽑는다.
최종적으로 해당 거인의 키가 센티의 키보다 작은지를 판별한다.

Python에서 지원하는 heapq 라이브러리는 아래와 같은 함수를 추가로 지원한다.

heapq.heapreplace(heap, elm) : 힙에서 가장 작은 원소를 뺀 뒤, 새로운 값을 넣음
heaqp.heappushpop(heap, elm) : 힙에서 특정 원소를 넣은 뒤, 가장 작은 원소를 뺌

처음에 거인의 키를 절반으로 줄인 후에 이를 다시 넣는 과정이 꽤나 번거로웠다.
그래서 관련 자료를 찾아보니 상단의 함수들이 더 존재한다는 것을 알게 되었다.

💻 Making Own Code

✅ Correct Code

import sys
import heapq

read = sys.stdin.readline
N, centi_height, T = map(int, read().split())

heap = [-int(read()) for _ in range(N)]
heapq.heapify(heap)

count = 0
for _ in range(T):
    if -heap[0] < centi_height or -heap[0] == 1:
        break
    heapq.heapreplace(heap, -(-heap[0] // 2))
    count += 1

if -heap[0] < centi_height:
    print('YES', count, sep='\n')
else:
    print('NO', -heap[0], sep='\n')