[BOJ] 백준 18111 - 마인크래프트 풀이

1. 문제

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

18111번: 마인크래프트

 

2. 풀이

백준 실버 2에 해당하는 브루트포스 문제이다. 개인적으론 실버 2가 아니라고 생각한다..
첫 번째로 주어진 입력을 받고 현재 블록의 최대 높이와 최소 높이를 미리 변수에 저장한다. 이를 저장하는 이유는 블럭을 0부터 256개까지 모두 탐색하는 것보다 최소부터 최대까지 탐색하면 탐색 횟수를 줄일 수 있기 때문이다.

모든 입력을 받고 나면 최소 값부터 최대 값까지 반복문을 돌면서 i 값을 인자로 받는 mineCraft()를 실행한다.
mineCraft 함수는 파라미터로 받은 i값으로 모든 블럭을 셋팅했을 때 걸리는 시간과 i값으로 객체를 리턴한다.

함수 안에서 가방을 백업해 두고 0부터 N - 1까지 반복문을 돌면서 현재 탐색하고자 하는 곳의 블럭을 i로 맞추는 작업을 시작한다.

(1) 현재 블럭 높이 - i (= 맞추려는 높이) > 0
이는 맞추려는 높이보다 현재 블럭 높이가 높으므로 이는 빼야 하는 곳이다. 블럭을 빼서 가방에 넣는 것은 2초가 걸리므로 뺀 갯수만큼의 시간을 더하고 뺀 블럭을 인벤토리에 넣는다.

(2) 현재 블럭 높이 - i (= 맞추려는 높이) < 0
이는 맞추려는 높이가 현재 블럭보다 높으므로 이는 인벤토리에서 블럭을 빼서 더해야하는 곳이다. 블럭을 쌓는 것은 1초가 걸리므로 쌓아야 하는 갯수만큼의 시간을 더하고 그 개수만큼 블럭을 뺀다.

한 번 2중 for문을 돌고 나면 반복문의 인덱스만큼 다 맞춘 것이다. 이때 가방의 블럭의 개수를 확인해야 한다. 
반복문 로직에서 블럭을 뺄 수 없는 경우(가방에 블럭이 없는데 빼서 쌓은 경우)를 처리해주지 않았기 때문에, 만약 이때 인벤토리에 블럭의 개수가 음수라면 mineCraftObjectList에 넣지 않고 0보다 크거나 같다면 리스트에 넣는다.
리스트에 넣는다는 것은 모든 블럭의 높이를 하나의 수로 맞췄다는 것이다.

이제 main에서 최소 시간이 걸리는 경우를 찾아야 하므로 리스트를 Comparator로 시간을 기준으로 오름차순 정렬 후 0번째 인덱스의 객체의 시간과 높이를 출력하면 정답!!! 

 

3. 소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;

public class Main {
    static int N, M, B;
    static int[][] map;

    static class mineCraftObject {
        int time;
        int height;

        public mineCraftObject(int time, int height) {
            this.time = time;
            this.height = height;
        }
    }
    // 탐색을 하면서 시간과 높이를 저장할 객체 List
    static List<mineCraftObject> mineCraftObjectList = new ArrayList<>();

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

        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        B = Integer.parseInt(st.nextToken());

        map = new int[N][M];

        int max = 0;  // 최소 블록 높이
        int min = 0;  // 최대 블록 높이

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < M; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());

                if (i == 0 && j == 0) {
                    max = min = map[i][j];
                } else {
                    if (max < map[i][j]) {
                        max = map[i][j];
                    } else if (min > map[i][j]) {
                        min = map[i][j];
                    }
                }
            }
        }

        for (int i = min; i <= max; i++) { // i 높이로 맞춘다고 생각하고 반복문을 돈다.
            mineCraft(i);
        }

        // 탐색을 끝낸 후 시간에 대하여 오름차순 정렬 ( 만약 시간이 같다면 높이로 정렬 )
        Collections.sort(mineCraftObjectList, new Comparator<mineCraftObject>() {
            @Override
            public int compare(mineCraftObject o1, mineCraftObject o2) {
                if (o1.time == o2.time) {
                    return o2.height - o1.height;
                }
                return o1.time - o2.time;
            }
        });

        bw.write(Integer.toString(mineCraftObjectList.get(0).time) + " " + Integer.toString(mineCraftObjectList.get(0).height));
        bw.flush();
        bw.close();
        br.close();
    }

    private static void mineCraft(int i) {
        int timeTemp = 0;
        int bag = B;

        for (int j = 0; j < N; j++) {
            for (int k = 0; k < M; k++) {
                int standardHeight = map[j][k] - i; // 현재 탐색하고 있는 map의 자리가 i 높이가 되기위해
                                                    // 채워야 하는지, 빼야하는지를 알 수 있게 하기 위한 값
                if (standardHeight > 0) {  // 현재 위치의 블럭 높이가 i보다 높으므로 빼야한다.
                    int absHeight = Math.abs(standardHeight);
                    timeTemp += (2 * absHeight);
                    bag += absHeight;
                } else if (standardHeight < 0) { // 현재 위치의 블럭 높이가 i보다 낮으므로 더해야 한다.
                    int absHeight = Math.abs(standardHeight);
                    timeTemp += Math.abs(absHeight);
                    bag -= Math.abs(absHeight);
                }
            }
        }

        // 탐색을 끝내고 난 후 가방에 있는 블록의 개수가 0보다 크거나 같아야함 (음수면 블럭을 안쓴게 된 것!!)
        if (bag >= 0) {
            mineCraftObjectList.add(new mineCraftObject(timeTemp, i));
        }
    }
}

 

4. 배운점

1. 브루트포스의 기본을 잘 생각하자!! (= 모든 블럭을 높이로 맞춰야 하므로, 기준 인덱스보다 현재 블럭의 높이가 크거나 작은지 확인!!)
2. 객체에 넣고 돌리는 것보다 time 자체를 계속 최솟값으로 갱신한다면 comparator를 해줄 필요가 없을 것 같다.(여기서 시간을 많이 줄일 수 있을 듯)