[백준] 26215 눈 치우기 - 탐욕법(Greedy) + 우선순위큐(PriorityQueue) JAVA

https://www.acmicpc.net/problem/26215

코드설명

탐욕법(Greedy) + 우선순위큐(PriorityQueue) 를 활용합니다.

 

항상, 가장 높은 눈을 가진 집과 그 다음 높은 눈을 가진 집을 기준으로 눈을 치워야, 최대한 많이 집 2개를 칠할 수 있습니다.

처음에는 눈을 치운이후에도, 계속해서 눈이 많은 곳을 기반으로 하는 것을 못알아채고, 투포인터 방식, 해시맵을 활용과 같은 방법으로 코드를 작성했지만 계속해서 오답이 발생했고, 눈을 치운 이후에도 계속해서 눈이 가장 많은 부분을 기준으로 작업해야 한다는 것을 깨닫고, 이후에는, PQ를 활용하여 가장 많은 눈을 기준으로 작업했습니다.

코드

package Main;

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 Main {
	private static int N, K, M;
    private static int answer = 0;
    private static int[] arr;
    private static PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
     
        N = Integer.parseInt(st.nextToken());
        arr = new int[N];
        st = new StringTokenizer(br.readLine());
        for(int i=0;i<N; i++) {
        	arr[i] = Integer.parseInt(st.nextToken());
        	pq.offer(arr[i]);
        }
        
        while(pq.size() > 1) {
        	int max = pq.poll();
        	int max2 = pq.poll();
        	answer += max2;
        	
        	if(max - max2 > 0) {
        		pq.offer(max - max2);
        	}
        }
        
        if(pq.size() == 1)
        	answer += pq.poll();
        
        if(answer > 1440) System.out.println(-1);
        else System.out.println(answer);
        
    }
    
}