[백준] 19638 파이썬(python) : 센티와 마법의 뿅망치 - 최대 힙 활용문제

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

19638번: 센티와 마법의 뿅망치

 

 

import sys, heapq
n, h, t = map(int, sys.stdin.readline().split())
giant = [ -1*int(sys.stdin.readline()) for _ in range(n) ] #1
heapq.heapify(giant) #2
cnt = 0
for _ in range(t):
    tmp = heapq.heappop(giant) #3
    if abs(tmp) < h: #4
        heapq.heappush(giant, tmp)
        break
    elif abs(tmp) == 1: #5
        heapq.heappush(giant, tmp)
    else: #6
        tmp = -(abs(tmp)//2)
        heapq.heappush(giant, tmp)
        cnt += 1
if abs(min(giant)) < h: #7
    print('YES')
    print(cnt)
else: #8
    print('NO')
    print(abs(heapq.heappop(giant)))

 

#1 : 최대 힙 정렬을 위해 -1을 곱해준 값을 삽입

#2 : 리스트 giant를 힙 자료구조로 변경

#3 : giant[0]을 빼줌 -1 곱해준 상태라서 음수값

#4 : abs() 사용한 최대값이 h보다 작으면 다시 넣어주고 break

#5 : 절댓값을 한 값이 뿅망치를 더 이상 쓸 수 없는 1일때는 다시 넣어줌

#6 : 절댓값을 취하고 /2 한뒤 음수를 삽입 그리고 횟수 1추가

(음수를 나누기 2를 하게되면 다른값이 나오게 됨)

#7 : 리스트 giant에 들어가 있는 값들은 음수이므로 가장 작은 값의 절댓값은 최댓값이 된다.

그 최댓값이 h보다 작다면 YES와 뿅망치 사용횟수 출력

#8 : 아니라면 NO와 heap[0]에 있는 가장 큰 값을 출력

 

최대 힙을 활용하는 문제는 처음 풀어본다. 몇 문제 더 풀면서 활용법을 익히도록 하자.

 

참고한 블로그

https://ki7348.tistory.com/85