항해99 리부트코스 알고리즘 2주 2일차 백준 19638 센티와 마법의 뿅망치

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

 

 

 

 

풀이

 

 

• 주어진 거인의 키들을 최대 힙(max heap)으로 관리
• 최대 힙을 사용하여 가장 큰 거인을 찾아 뿅망치로 줄임
• 이를 T번 반복하거나, 모든 거인의 키가 H이하가 되면 중지

 

import heapq
import sys

input = sys.stdin.readline

def solve(n, h, t, giants):
    # 거인들의 키를 최대 힙으로 변환 (음수로 저장하여 최대 힙처럼 동작하게 함)
    max_heap = [-giant for giant in giants]
    heapq.heapify(max_heap)
    
    count = 0  # 뿅망치 사용 횟수 카운트
    for _ in range(t):  # 최대 T번 반복
        largest = -heapq.heappop(max_heap)  # 현재 가장 큰 거인의 키를 가져옴 (최대 힙에서 음수로 저장되어 있으므로 다시 양수로 변환)
        if largest < h:  # 가장 큰 거인의 키가 센티의 키보다 작으면 종료
            heapq.heappush(max_heap, -largest)  # 힙에 다시 넣어줌
            print("YES")
            print(count)
            return
        if largest == 1:  # 거인의 키가 1이면 더 이상 줄일 수 없음
            heapq.heappush(max_heap, -largest)  # 힙에 다시 넣어줌
            break
        largest //= 2  # 거인의 키를 절반으로 줄임
        heapq.heappush(max_heap, -largest)  # 줄인 키를 다시 힙에 추가
        count += 1  # 뿅망치 사용 횟수 증가

    maxV = -max_heap[0]  # 뿅망치 사용 후 가장 큰 거인의 키
    if maxV < h:  # 최종적으로 가장 큰 거인의 키가 센티의 키보다 작으면
        print("YES")
        print(count)
    else:
        print("NO")
        print(maxV)


n, h, t = map(int, input().split())  # 거인의 수, 센티의 키, 뿅망치 사용 횟수 입력
giants = [int(input()) for _ in range(n)]  # 각 거인의 키 입력

solve(n, h, t, giants)

 

 

• 입력받은 거인의 키를 최대 힙으로 변환. 최대 힙을 구현하기 위해 음수 값을 사용
• 뿅망치를 최대 TTT번 사용할 수 있도록 반복문을 설정
• 가장 큰 거인의 키를 가져와서 센티의 키보다 작은지 확인
• 뿅망치를 사용하여 거인의 키를 절반으로 줄임
• 모든 반복이 끝난 후, 최종적으로 가장 큰 거인의 키가 센티의 키보다 작아졌는지 확인