[백준-19638] 센티와 마법의 뿅망치

문제

링크

풀이

import sys
import heapq

input = sys.stdin.readline

n, h, t = map(int, input().split())

height = []
count = 0
for _ in range(n) :
    heapq.heappush(height, -int(input()))

for _ in range(t) :
    if -height[0] == 1 or -height[0] < h :
        break
    tmp_h = -heapq.heappop(height)
    if tmp_h > 1 :
        heapq.heappush(height, -(tmp_h/2))
    else :
        heapq.heappush(height, -1)
    count+=1

if -height[0] < h :
    print('YES')
    print(count)
else :
    print('NO')
    print(int(-height[0]))

키가 큰 거인부터 뿅망치를 이용해야 하므로 height라는 배열에 넣을 때 음수로 바꾸어 넣어준다. (파이썬에서 힙은 최소값으로 출력되기 때문에)

거인의 키가 1일 경우 영향을 줄 수 없기 때문에 break
-height[0] 이 거인들 중 가장 큰 키인데 센티의 키(h)보다 작으면 완료되었으므로 break

위의 조건에 모두 부합한다면 가장 큰 거인의 키를 1/2씩 줄이면서 count를 1씩 증가시킨다.
이때도 키가 1일 경우 그냥 1을 다시 넣어주고 count를 1씩 올리면 된다.

뿅망치 횟수가 모두 완료되거나 break로 인해 반복문이 종료될 경우 거인들 중 가장 큰 거인의 키가 센티의 키(h)보다 작을 경우 yes와 총 횟수를 출력하고, 그렇지 않을 경우 no와 가장 큰 거인의 키를 출력한다.