[백준] 18111번 마인크래프트 - JAVA

---

 

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

18111번: 마인크래프트

 

 

구현 문제다.

가장 높은 높이부터 0까지 위에서 아래로 차례대로 계산해주는 함수를 호출하며 내려갔다.

로직은 간단한데 구현이 오래 걸린다.

 

채울 때는 시간을 1초 추가해주는 것도 있지만,

박스가 충분한지 확인해줘야 한다.

 

출력은 가장 높은 높이의 값을 출력해줘야 해서 우선순위 큐를 사용했다.

 

 

---

코드

 

import java.io.*;
import java.math.BigInteger; // subtract , multiply, add, mod
import java.util.*;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static StringTokenizer st;
    static StringBuilder sb = new StringBuilder();

    static int[][] arr;
    static int[] temp;
    static int globalMin = Integer.MAX_VALUE;
    static int globalMax = Integer.MIN_VALUE;
    static int[] su;

    public static void main(String[] args) throws IOException {

        // 입력부
        StringTokenizer st = new StringTokenizer(br.readLine());
        int low = Integer.parseInt(st.nextToken());
        int col = Integer.parseInt(st.nextToken());
        int boxes = Integer.parseInt(st.nextToken());

        int maxHeight = 0;
        arr = new int[low][col];
        for(int i = 0 ; i<low; i++){
            st = new StringTokenizer(br.readLine(), " ");
            for(int j = 0; j<col; j++ ) {
                int num = Integer.parseInt(st.nextToken());
                arr[i][j] = num;
                maxHeight = Math.max(maxHeight, num);
            }
        }

        int ans = Integer.MAX_VALUE;
        Queue<HB> q = new PriorityQueue<HB>((o1, o2)->{
            if( o1.time == o2.time)
                return o2.height - o1.height;
            return o1.time - o2.time;
        });

        for(int i = maxHeight; i>=0; i--){
            int[] answer = findTime(i, boxes, arr);
            q.offer(new HB(answer[0], answer[1]));
        }
        System.out.println(q.poll());


    }
    public static int[] findTime(int height, int boxes, int[][] arr){
        int[] ans = new int[2];
        int time = 0;
        // 제거시간
        for(int i = 0 ; i<arr.length; i++){
            for(int j = 0; j<arr[0].length; j++){
                if(arr[i][j] > height){
                    int tt = arr[i][j] - height;
                    time += tt * 2; // 제거 2초
                    boxes += tt;
                }
            }
        }

        // 채우기 시간
        for(int i = 0 ; i<arr.length; i++){
            for(int j = 0; j<arr[0].length; j++){
                if(arr[i][j] < height){
                    int tt = height - arr[i][j];
                    time += tt; // 설치 1초
                    boxes -= tt;
                    if(boxes < 0) {
                        ans[0] =Integer.MAX_VALUE;
                        return ans;
                    }
                }
            }
        }
        ans[0] = time;
        ans[1] = height;
        return ans;
    }
}

class HB{
    int time;
    int height;
    public HB(int time, int height){
        this.time = time;
        this.height = height;
    }
    public String toString(){
        return this.time + " " + this.height;
    }
}