반응형
https://www.acmicpc.net/problem/19638
19638번: 센티와 마법의 뿅망치
마법의 뿅망치를 센티의 전략대로 이용하여 거인의 나라의 모든 거인이 센티보다 키가 작도록 할 수 있는 경우, 첫 번째 줄에 YES를 출력하고, 두 번째 줄에 마법의 뿅망치를 최소로 사용한 횟수
www.acmicpc.net
소스코드
풀이
★ 가장 키가 큰 거인의 키부터 반토막을 내기 위해 최대힙을 만들어줍니다.
★ 이후 반복문을 도는데, 키가 가장 큰 거인의 키가 센티의 키보다 크거나 같을 때를 보면, 1인 경우에는 더이상 쪼갤 수 없으며 최대힙인데도 가장 큰 거인의 키가 1이라는 것은 양의 정수 중 가장 작은 경우이기 때문에 break를 통해 반복문을 바로 빠져나옵니다. 이러한 코드가 없다면 예제로 주어진
1 1 100000
1
의 경우에 반복문을 계속해서 돌게 됩니다 !
★ 1인 경우가 아니라면 거인의 키를 1/2해서 다시 최대힙에 추가해줍니다. 이때 나머지를 취급하지 않기 위해 int형으로 추가하였습니다 !
★ 거인의 키가 더 작은 경우는 arr 배열에 남아있는 모든 요소도 키 또한 센티의 키보다 작을 것이기 break문으로 반복문을 종료합니다. (최대힙이기 때문에)
반응형
'Algorithm > 백준' 카테고리의 다른 글
| [백준 알고리즘] 2606번: 바이러스 (Python) (0) | 2023.09.22 |
|---|---|
| [백준 알고리즘] 1202번: 보석 도둑 (Python) (2) | 2023.08.23 |
| [백준 알고리즘] 23757번: 아이들과 선물 상자 (Python) (3) | 2023.08.22 |
| [백준 알고리즘] 1904번: 01타일 (Python) (2) | 2023.08.22 |
| [백준 알고리즘] 14235번: 크리스마스 선물 (Python) (0) | 2023.08.18 |