[Baekjoon] 19638_센티와 마법의 뿅망치

Silver I

문제(출처: https://www.acmicpc.net/problem/19638)

---

< 센티와 마법의 뿅망치 >

 

문제 풀이 

 

우선순위 큐를 내림 차순으로 초기화하여 제일 큰 거인의 키를 뿅망치 횟수 제한만큼 반으로 줄여준다.

 

 

 my solution (Java)

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Collections;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class _19638_ { // 센티와 마법의 뿅망치

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(bf.readLine());

		int n = Integer.parseInt(st.nextToken());
		int h = Integer.parseInt(st.nextToken());
		int t = Integer.parseInt(st.nextToken());

		PriorityQueue<Integer> queue = new PriorityQueue<>(Collections.reverseOrder());
		for (int i = 0; i < n; i++) {
			queue.add(Integer.parseInt(bf.readLine()));
		}

		boolean flag = false;
		for (int i = 0; i < t; i++) {
			if (queue.peek() < h) {
				bw.write("YES\n");
				bw.write(Integer.toString(i));
				flag = true;
				break;
			}
			if (queue.peek() == 1)
				break;
			int num = queue.poll();
			queue.add(num / 2);
		}

		if (!flag) {
			if (queue.peek() < h) {
				bw.write("YES\n");
				bw.write(Integer.toString(t));
			} else {
				bw.write("NO\n");
				bw.write(Integer.toString(queue.peek()));
			}

		}
		bw.flush();
	}
}

 

Main

변수)
n : 인구수
h : 센티의 키
t : 마법의 뿅망치의 횟수 제한
queue : 내림차순 우선순위 큐

 

- 인구수(n), 센티의 키(h), 마법의 뿅망치의 횟수 제한(t) 입력

- 거인의 키를 입력받아 queue에 저장

- 마법의 뿅망치의 횟수 제한(t)만큼 뿅망치 사용

1) queue의 맨 앞에 있는 값이 h보다 작다면 모든 거인이 센티보다 키가 작다는 뜻이므로 "YES"와 뿅망치를 최소로 사용한 횟수 출력

2) queue의 맨 앞에 있는 값이 1이라면 더 이상 줄어들지 않으므로 종료

3) queue에서 값을 꺼내와 값을 반으로 줄여 queue에 저장

- 뿅망치를 다 사용하고 난 후에 센티보다 키가 작다면 "YES"와 뿅망치를 최소로 사용한 횟수 출력

  센티보다 키가 크다면 "NO"와 가장 키 큰 거인의 키 출력

 

---

---