[백준] 19638 센티와 마법의 뽕망치 파이썬 풀이

※ 사용언어 : 파이썬 ※

 

▼ 문제 링크 ▼

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

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

 

 

---

 

고려사항

1. 키가 1인 경우 더 이상 줄어들 수 없기 때문에 뽕망치의 영향을 받지 않는다

2. 거인의 최대키가 센티의 키보다 작으면 더 이상 뽕망치를 쓸 이유가 없으므로 멈춰줘야 한다.

3. 힙을 통해 풀 경우, 해당 문제를 풀기 위한 힙은 최대 힙이 되어야 하지만, 파이썬은 최소 힙만 제공해준다. 그래서 -1을 곱해 최대 힙으로 접근할 수 있도록 한다.

(예를 들어 1과 2가 있는 경우 -가 붙지 않으면 1이 최솟값이지만 -가 붙으면 2가 최소값이 된다. 이런 식으로 -를 붙여 최댓값을 최솟값으로 바꿔서 힙을 구현하는 것이다.)

 

 

---

 

문제풀이 (With Python)

import heapq
import sys

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

height=[]
for i in range(N):
    heapq.heappush(height,-(int(sys.stdin.readline())))

count=0

for j in range(T):
    magic=heapq.heappop(height)*-1
    if magic==1:
        heapq.heappush(height,-1)
    elif magic<H:
        heapq.heappush(height,magic*-1)
        break
    else:
        heapq.heappush(height,(magic//2)*-1)
        count+=1

final=heapq.heappop(height)*(-1)
if final>=H:
    print("NO")
    print(final)
else:
    print("YES")
    print(count)

◇ heap에 거인들의 키 값을 넣을 때 -를 곱해 음수로 만들어 넣어준다.

 

◇ 두 번 째 for문을 통해 거인의 키와 센티의 키를 비교할 때는 -를 곱해 양수로 바꿔서 비교한다. 비교 후 heap에 push할 때는 다시 -1를 곱해 음수로 바꿔준다.

 

◇ 두번 째 for문을 순회 중 거인의 키보다 센티의 키가 크면 꺼낸 거인의 키 값을 다시 넣어주고 break로 빠져나온다.

 

◇ 마지막에 final로 최종 거인의 키를 출력할 땐 다시 -를 곱해 양수로 바꿔준다.