[Baekjoon] 26215_눈 치우기

Silver III

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

---

< 눈 치우기 >

 

문제 풀이 

 

우선순위 큐를 사용해서 눈의 양이 큰 순서대로 우선순위를 둔다. 눈의 양이 큰 집부터 눈을 치운다.

 

 

 my solution (Java)

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

public class _26215_ { // 눈 치우기

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

		int n = Integer.parseInt(bf.readLine());

		st = new StringTokenizer(bf.readLine());
		PriorityQueue<Integer> queue = new PriorityQueue<>(Collections.reverseOrder());

		for (int i = 0; i < n; i++) {
			queue.add(Integer.parseInt(st.nextToken()));
		}

		int result = 0;
		while (!queue.isEmpty()) {
			int a = queue.poll();

			if (queue.isEmpty()) {
				result += a;
				break;
			}
			int b = queue.poll();
			result += b;
			queue.add(a - b);
		}

		if (result > 1440)
			System.out.println(-1);
		else
			System.out.println(result);
	}
}

 

Main

변수)
n : 집의 수
queue : 우선순위 큐 (내림차순)
result : 모든 집 앞의 눈을 치우는 데 시간

 

우선순위 큐에 눈의 양이 많은 순서대로 정렬한다.

 

눈의 양이 가장 많은 집을 뽑고 집이 하나밖에 남지 않았다면 그 눈의 양이 시간이 된다. 다른 집도 있다면 한 집을 더 뽑아 두 번째 집 눈의 양만큼 눈을 치우고 다시 우선순위 큐에 넣는다.

이 과정을 반복하면 모든 집 앞의 눈을 치우는 데 걸리는 시간을 구할 수 있다.

---

---