[알고리즘-PS] 백준 18111번 마인크래프트 자바 문제풀이

문제

해당 포스팅은 백준의 18111번 마인크래프트 의 접근과 해결 방법을 설명한 글 입니다.
정답 소스 코드를 확인하시려면 solve url 에서 확인 가능합니다.

18111번: 마인크래프트

 

이 문제를 해결하기 위해 어떤 방식으로 접근해야 하는지를 먼저 생각해보자.

 

문제 접근

 

이번 문제는 입력을 보고 어떤 알고리즘으로 풀어야할지 알 수 있다.

 

 

우선 배열은 500 x 500 크기의 배열이 들어오고 B 에는 최대 6억 4천의 블록이 존재할 수 있다.

 

그럼 최악의 경우 n의 3제곱이 1천만 정도 되니 브루트 포스 알고리즘을 이용해서 문제를 해결할 수 있게 된다.

 

브루트포스 알고리즘으로 모든 경우를 확인하더라도 충분히 커버가 가능하다.

 

해결법

 

이 문제의 해결 방법은 브루트포스로 0층 부터 256층까지 모든 블럭을 평평하게 만드는데 필요한 시간의 최소를 매번 비교하면 된다.

 

조금 더 생각을 해보면 0층 부터가 아니라 존재하는 블록 중 가장 작은 층 에서 존재하는 블록중 가장 높은 층 사이에 범위만 가능하므로 입력을 받을 때 최소와 최대 높이를 각각 지정하고 층수 반복을 돌 때 해당 최대 최소를 기준으로 돌면 된다.

정답 코드

public class B18111 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        String[] nmb = br.readLine().split(" ");
        int n = Integer.parseInt(nmb[0]);
        int m = Integer.parseInt(nmb[1]);
        int b = Integer.parseInt(nmb[2]);

        int[][] ground = new int[n][m];

        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;

        for (int i = 0; i < ground.length; i++) {

            String[] groundRow = br.readLine().split(" ");

            for (int j = 0; j < m; j++) {
                int value = Integer.parseInt(groundRow[j]);
                ground[i][j] = value;

                max = Math.max(max, value);
                min = Math.min(min, value);
            }
        }

        int answerSeconds = Integer.MAX_VALUE; // 시간
        int answerHeight = -1; // 층

        for (int i = min; i <= max; i++) { // 최소층 부터 최대층 까지

            int seconds = 0;
            int inventory = b;

            for (int j = 0; j < ground.length; j++) {
                for (int k = 0; k < ground[j].length; k++) {
                    int diff = ground[j][k] - i;

                    if(diff > 0) { // 제거해야 함
                        seconds += Math.abs(diff) * 2;
                        inventory += Math.abs(diff);
                    }else if(diff < 0){ // 추가해야 함
                        seconds += Math.abs(diff);
                        inventory -= Math.abs(diff);
                    }
                }
            }

            if(inventory >= 0) {
                if(seconds <= answerSeconds) { // == 가 포함되어야 함 ㅇ그렇지 않으면 최대 높이를 판별 하지 못함
                    answerSeconds = seconds;
                    answerHeight = i;
                }
            }
        }

        bw.write(answerSeconds + " " + answerHeight);

        bw.flush();
        bw.close();
    }
}

 

정답 소스 코드를 확인하시려면 solve url 에서 확인 가능합니다.