마인크래프트

문제

풀이

package baekjoon.class_.class2.마인크래프트;


import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.HashMap;

public class Main {

    static BufferedReader br;
    static BufferedWriter bw;
    static int y;
    static int x;
    static HashMap<Integer, Integer> map = new HashMap<>();
    static int inven;

    static Integer[] heightListAsc;

    static int resultSecond = Integer.MAX_VALUE;
    static int resultHeight;

    public static void main(String[] args) throws Exception {
        br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));
        String[] s = br.readLine().split(" ");
        y = Integer.parseInt(s[0]);
        x = Integer.parseInt(s[1]);
        inven = Integer.parseInt(s[2]);
        for(int i = 0; i<y; i++){
            String line[] = br.readLine().split(" ");
            for(int j = 0; j<x; j++){
                int height = Integer.parseInt(line[j]);
                map.put(height, map.getOrDefault(height, 0)+1);
            }
        }
        heightListAsc = map.keySet().toArray(new Integer[0]);
        Arrays.sort(heightListAsc);
        sol();
        bw.write(resultSecond + " " + resultHeight);
        bw.flush();
    }

    static void sol(){
        for(int i = 0; i<=256; i++){
            sol(i);
        }
    }

    static void sol(int targetHeight){
        int result = 0;
        int inventory = inven;
        for(int height = heightListAsc[heightListAsc.length-1]; heightListAsc[0]<=height; height--){
            if(targetHeight < height){
                int gap = height - targetHeight;
                int k = map.getOrDefault(height,0);
                result += gap * k * 2;
                inventory += k * gap;
            }else if(height < targetHeight){
                int k = map.getOrDefault(height,0);
                int gap = targetHeight - height;
                if(inventory < k*gap) return;
                inventory -= k*gap;
                result += gap * k;
            }
        }

        if(result < resultSecond){
            resultSecond = result;
            resultHeight = targetHeight;
        }else if(result == resultSecond){
            resultHeight = Math.max(resultHeight, targetHeight);
        }
    }
}

풀이 설명

문제 자체가 어렵진 않았다. 평탄화할 높이를 0부터 256까지의 상황으로 각각 계산하고, 그 중 가장 적은 시간이 드는 케이스를 찾으면 되는 문제였다.

처음에는 문제에서 주어진 대로 이차배열로 지도를 그려 이차배열을 순회화며 답을 찾는 방식을 생각했으나, 최대 256 x 500 x 500 번의 순회가 발생하기 때문에 TimeOver 날 것이라 생각했고, 이게 문제의 함정이라고 생각해 다른 방법을 생각하게 되었다.
(그런데 다른 블로그들을 찾아보니 이차배열로 순회해도 TimeOver가 나지 않는 것 같다)

256번의 케이스동안 매번 이차배열을 순회하는 대신, map을 사용해 같은 높이의 블럭이 몇 개 있는지 기록하고, 각 블럭 높이에 따라 case와 대조하여 답을 구하는 식으로 접근하였다.

이차배열을 꼭 순서대로 순회해야하는 것은 아니기 때문에 위와 같이 그냥 같은 높이의 블럭들을 전부 묶어 하나의 케이스로 분류하고, 같은 높이의 블럭 수 만큼 시간초를 곱해주면 동일한 결과를 얻을 수 있기 때문이다.

시간비교

이차배열을 순회할 시 3중 for문을 돌아야 하고, 위의 방법을 이용하면 2중 for문으로 문제를 해결할 수 있다.

위는 3중 for문, 아래는 2중 for문을 이용한 풀이로 두 방법 간에는 약 250ms정도가 차이나는 모습을 볼 수 있다.

250ms면 알고리즘에서 적은 차이는 아니긴 하지만
주어진 최대 값이 256이나 500정도로 크지 않아 생각만큼 드라마틱한 차이가 나타나지는 않는 것 같다

참고로, 3중 for문을 돌리는 경우 6400만번을 순회하는데 오버헤드 포함 0.8초 정도 걸리는 것을 봐서
약 1억번 조금 안되는 순회를 돌아야 1초의 조건에서 timeout이 나는 것 같다.