[백준 시리즈] 19638번 : 실버 1 - 센티와 마법의 뿅망치 / Python

제목 : 센티와 마법의 뿅망치

출처 : 백준 /  https://www.acmicpc.net/problem/19638

사용 자료구조&알고리즘 : 힙

 

문제 설명

1. 횟수 제한이 있는 뿅망치를 전략대로 이용하여 모든 거인이 센티보다 키가 작도록 만들 수 있는지 구한다.

2. 전략은 매번 가장 키가 큰 거인 가운데 하나를 때리는 것이다.

3. 키가 1인 경우를 제외하고, 뿅망치에 맞은 거인은 키가 floor(맞은 사람의 키 / 2)가 된다.

4. 전략이 먹히는 경우 YES와 최소 뿅망치 횟수를 출력하고, 전략이 먹히지 않는 경우 NO와 가장 큰 거인의 키를 출력한다.

 

제한

시간 제한 : 1초 (최대 약 2000만번의 연산)

메모리 제한 : 1024 MB

인구수 N (1<=N<=10^5)

센티의 키 H (1<=H<=2*10^9)

뿅망치 횟수 T (1<=T<=10^5)

 

문제 풀이

1단계 : 최대 시간복잡도는 얼마인가?

N*T = 10^10 이므로 O(NlogN)이하의 시간복잡도가 요구된다.

 

2단계 : 핵심 아이디어는 무엇인가?

본문에서 제시된 전략을 그대로 시뮬레이션 하되 힙을 적용하여 시간복잡도를 감소시킨다.

 

정답 코드

import heapq as hq
n, h, t = map(int, input().split())
q = []
smash_cnt = 0

for _ in range(n):
    hq.heappush(q, -int(input()))

for _ in range(t):
    x = -hq.heappop(q)
    if x >= h: smash_cnt += 1
    if x > 1: x //= 2
    hq.heappush(q, -x)

x = -hq.heappop(q)
if x < h:
    print("YES")
    print(smash_cnt)
else:
    print("NO")
    print(x)

* heapq는 기본적으로 minheap이며 데이터를 음수로 삽입하면 maxheap으로 바꿀 수 있다.

* floor(-127 / 2) = -64 임에 주의하자.

* 키가 같아도 안됨에 주의하자.