[알고리즘/자료구조] 19638번 : 센티와 마법의 뿅망치 - python

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

 

 

---

• 문제
• 소요시간: 17분 53초

---

• 설계하기(접근방법) 

1. 입력받기

입력이 10만개이니 sys를 통해 입력받는다

 

2. 구현하기

 

가장 키가 큰 거인에게 망치를 쓴다는 조건이 주어졌다

거인이 10만명이니 리스트에서 매번 큰 거인을 찾는다면 시간이 초과될 것이다

 

따라서 heapq를 사용하여 가장 키가 큰 거인을 빠르게 찾을 수 있도록 구성해야 한다

 

입력받은 거인의 키에 (-1)을 곱해 거인의 키를 heappush 해준다

 

거인의 키가 입력되었으면 시도만큼 망치를 때리면서 1/2 floor을 해준다

 

문제에서 키가 1인 경우에는 더 이상 줄어들징 않는다고 했으니,

망치를 치기 전에 가장 키가 큰 거인의 크기가 1인지 아닌지 검사해야한다.

while문을 통해 위의 논리를 구성해주자

 

3. 출력하기

다 쳤음에도 가장 큰 거인의 키가 센티보다 크다면 NO와 거인의 키를,

어느 순간 가장 큰 거인의 키보다 크면 종료하고, YES와 친 횟수를 출력해준

 

---

• 코드(출력)

import heapq, sys
input = sys.stdin.readline

population, height, trial = map(int, input().split())
trial_original = int(trial)
big = []


for _ in range(population):
    heapq.heappush(big, -int(input()))

while trial:
    if big[0] == -1:
        break
    if -big[0] < height:
        break
    biggest = -(heapq.heappop(big))
    half = biggest // 2
    heapq.heappush(big, -half)
    trial -= 1


if -big[0] < height:
    print("YES")
    print(trial_original -  trial)
else:
    print("NO")
    print(-big[0])

---

• 얻어갈 부분

1. 오랜만에 알고리즘, 자료구조 문제를 풀어 heap 문법을 다시 생각해낼 수 있었다.