백준 19638번 - 센티와 마법의 뿅망치

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

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

 

 

 

• 접근 방법

처음 문제를 보고 가장 키가 큰 거인에게 지팡이를 사용하고 줄어든 키를 다시 저장하기를 반복하며 centi의 키와 비교하자고 생각했고, 가장 큰 수를 앞에 저장하는 자료구조를 생각했는데 바로 최대 힙이었다. 특별한 순서 없이 가장 큰 수를 다루기에 가장 적합하다고 생각했다.

 

 

 

• 논리 흐름(알고리즘)

최대힙에 거인들의 키를 모두 저장 후

가장 키가 큰(최대 힙의 top) 거인에게 지팡이를 사용했을 때 /2해준 값을 최대힙에 새로 최신화해주었다.

이 과정에서 centi의 값이 최대 힙의 top보다 커지면 조건에 만족하기 때문에 YES의 경우로 출력해주고 끝난다.

만약 지팡이를 모두 사용하였지만 centi값이 최대 힙의 top보다 작을 경우 NO의 경우로 출력해준다.

이 때 주의할 점은 지팡이를 사용하기도 전에 이미 centi의 키가 가장 클 경우를 위해 YES의 경우를 앞에 써 주고,

지팡이 사용의 마지막에 centi의 키가 가장 커질 경우를 위해 반복문 밖에도 YSE의 경우를 출력해주었다.