https://www.acmicpc.net/problem/19638
19638번: 센티와 마법의 뿅망치
마법의 뿅망치를 센티의 전략대로 이용하여 거인의 나라의 모든 거인이 센티보다 키가 작도록 할 수 있는 경우, 첫 번째 줄에 YES를 출력하고, 두 번째 줄에 마법의 뿅망치를 최소로 사용한 횟수
www.acmicpc.net
풀이 방법
우선순위 큐를 사용하였다.
- 키가 큰 것을 우선으로 하는 최대힙 우선순위 큐를 생성한다.
- N의 거인들의 키를 모두 큐에 삽입한다.
- 즉, 큐에서 peek한 요소는 키가 가장 큰 거인의 키가 된다.
- time = 0 부터 최대 T가 될 때까지 큐에서 하나씩 꺼내면서 뿅망치 때리기를 반복한다.
- 큐에서 peek 한 키가 H보다 작거나 1이라면 바로 반복문을 탈출한다.
- 그게 아니라면 poll 하여 키를 꺼내고 2로 나눈 키를 다시 큐에 삽입한다.
- time을 증가시키고 다시 뿅망치 작업을 한다.
- 반복문이 끝난 뒤 큐에서 peek 한 요소가 H보다 작다면 "YES"와 함께 time 값을 출력한다.
- H보다 같거나 작다면 "NO"와 함께 peek한 요소를 출력한다.
코드
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] line = br.readLine().split(" ");
int N = Integer.parseInt(line[0]);
int H = Integer.parseInt(line[1]);
int T = Integer.parseInt(line[2]);
PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
for(int i=0; i<N; i++) {
int height = Integer.parseInt(br.readLine());
pq.add(height);
}
int time = 0;
while(time < T) {
int height = pq.peek();
if(height < H || height == 1) {
break;
}
pq.add(pq.poll() / 2); // 뿅망치로 맞은 후 키 삽입
time++;
}
if(pq.peek() < H) {
System.out.println("YES");
System.out.println(time);
} else {
System.out.println("NO");
System.out.println(pq.peek());
}
}
}
'알고리즘 > baekjoon' 카테고리의 다른 글
| 백준 21315 카드 섞기 자바(java) (2) | 2024.01.30 |
|---|---|
| 백준 16166 서울의 지하철 자바(java) (0) | 2024.01.30 |
| 백준 17281 야구⚾ 자바(java) (0) | 2024.01.29 |
| 백준 12764 싸지방에 간 준하 자바(java) (0) | 2024.01.27 |
| 백준 7682 틱택토 자바(java) (0) | 2024.01.26 |