잡담.
다른 글을 쓰다가 시간이 없어서 급하게 백준에서 랜덤다이스를 돌려서 뽑았다. 처음에 실버1 치고 되게 쉬운데? 하면서 최대힙을 응용해서 푼 문제.
풀이가 눈에 보여서 빠르게 제꼈지만 한가지 빼먹기 쉬운 점이 있는데 반드시 체크를 할 필요가 있다.(이거때문에 정답률 33%에 실버1인 것 같다.. 난이도 자체는 실버3 미만(?))
문제 설명.
centi와 거인들이 있고, centi는 요술방망이를 가지고 있다. 이 요술방망이는 횟수 제한(T)이 있고, 거인을 한번 때릴 때 거인의 키(in 자연수)를 정수 단위로 이등분하는 요술몽둥이이다. 다만 키가 1인 경우 요술방망이의 효과가 없다고 가정하자.
(키가 0이면 존재성의 문제가..)
- ex1. 거인
X가 있어서 키가 31일 때 요술방망이를 1대 맞으면X의 키는31//2 = 15가 된다. - ex2. 키가 1인 거인에게 요술방망이를 휘둘러봐야 키가 1이다.
centi는 거인들의 키가 자기보다 큰 것이 싫어서 최대한 거인들을 난쟁이로 만들려고 한다. 요술방망이는 귀중한 자산이기 때문에 centi는 요술방망이의 사용 전략을 짜서 한번 사용할 때 마다 재일 키가 큰 거인에게 요술방망이를 쓸 할 예정이다.
입/출력.
입력.
N centi_height T(요술방망이를 사용할 수 있는 횟수)
(N개의 줄 동안 거인들의 키)출력.
출력은 2가지 케이스로 나뉘어져 있다.
- 요술방망이를 사용하다가 키가 가장 큰 거인의 키가 centi보다 작아지는 경우.
YES
(요술방망이를 사용한 횟수)- 요술방망이를 다 사용했는데도 키가 가장 큰 거인의 키가 centi의 키보다 크거나 같은 경우.
NO
(키가 가장 큰 거인의 키)
문제 풀이.
잡담에서 말했듣이 최대힙을 응용해서 풀었다.
가장 키가 큰 거인을 선택해야 하기 때문에 간단히 heapq에 들어가는 원소에 -를 붙여서 집어넣었고, 뽑아서 쓸 때는 -를 곱해서 사용한다.(코드상에서는 heappush 안쪽에 한번에 가져다 박았다.)
그리고 방망이를 사용한 직후마다 max(거인의 키)<centi의 키가 되는지를 체크해주고 만약 이게 된다면 첫 번째 출력 후 종료, 끝까지 안된다면 두 번째 출력 후 종료를 하면 된다.
- 풀이 코드.
from sys import stdin
import heapq
N,H_centi,T = map(int,stdin.readline().strip().split())
giants = []
for _ in range(N):
heapq.heappush(giants,-int(stdin.readline()))
# if -giants[0]<H_centi:
# print('YES')
# print(0)
# exit(0)
for i in range(1,T+1):
heapq.heappush(giants,-max(1,(-heapq.heappop(giants))//2))
if -giants[0]<H_centi:
print('YES')
print(i)
exit(0)
print('NO')
print(-giants[0])처음 제출하고 이왜틀?을 외치고, 곰곰히 생각해본 결과 위의 코드에서 주석처리된 부분이 틀린 것이었다. 단순하게, 몽둥이질을 하지 않은 케이스가 고려되지 않았더라.. 백준의 질문에 예시를 적어놨는데 혹시라도 다 풀고 이왜틀? 하는 사람이 있다면 이 경우를 체크해보길...
