[백준] 26215번 눈 치우기 (Java)

0. 출처

백준 26215번 문제입니다.

 

1. 문제

지난 밤 겨울 숲에는 눈이 많이 내렸다. 당신은 숲의 주민들을 위해 눈이 오지 않는 동안 모든 집 앞의 눈을 치우고자 한다. 당신은 1분에 한 번씩 두 집을 선택해서 두 집 앞의 눈을 각각 1만큼 치우거나, 한 집을 선택해서 그 집 앞의 눈을 1만큼 치울 수 있다. 모든 집 앞의 눈을 전부 치울 때까지 걸리는 최소 시간은 얼마일까?

(1) 입력

첫 줄에 집의 수를 의미하는 정수 N(1≤N≤100) 이 주어진다.

다음 줄에는 각각의 집 앞에 쌓여 있는 눈의 양을 나타내는 정수 a(1≤a≤2000) 이 주어진다.

(2) 출력

모든 집 앞의 눈을 치우는 데 최소 몇 분이 걸리는지를 출력한다. 24시간(1440분)이 넘게 걸릴 경우 -1을 출력한다.

 

2. 문제 풀이

(1) 문제 풀이 방법

집 앞의 눈을 모두 치울 때까지 걸리는 최소 시간을 구하는 문제이므로, 최대한 두 집을 함께 치우는 것이 좋습니다.

가장 눈이 많이 쌓여있는 집을 찾아 그 집과 그 다음 집을 함께 치우는 것이 최소 시간이 걸리는 방법이겠죠!

 

저는 우선순위 큐를 활용했고, Collections.reverseOrder()를 활용해서 내림차순 정렬을 했습니다. 집이 하나 남아있을 때에는 그 집만 치우면 되므로 남은 눈의 양을 time 변수에 모두 더해주면 됩니다. 집이 두 개 이상 남아있는 경우에는 가장 눈이 많이 쌓인 두 집을 꺼내 1씩 차감한 후, 다시 큐에 넣어주는 방식을 큐가 빌 때까지 반복해주면 됩니다!

(2) 코드 (Java)

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        PriorityQueue<Integer> q = new PriorityQueue<>(Collections.reverseOrder()); // 내림차순 정렬
        for(int i=0; i<N; i++) {
            q.add(Integer.parseInt(st.nextToken()));
        }
        
        int time = 0;
        while(!q.isEmpty()) {
            if(time>1440) break;
            
            if(q.size() == 1) { // 남은 집이 하나인 경우
                int h = q.poll();
                time += h;
                break;
            }
            
            int h1 = q.poll();
            int h2 = q.poll();
            
            if(h1-1 > 0) q.add(h1-1);
            if(h2-1 > 0) q.add(h2-1);
            
            time++;
        }
        
        if(time > 1440) time = -1;
        System.out.println(time);
        br.close();
    }
}

 

(3) 결과