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

문제 설명

 

18111번: 마인크래프트

 

풀이 회고

제가 해당 문제를 풀기 위한 접근 방법은 다음과 같았습니다.

 

1. 주어진 2차원 배열 상의 요소별 값(집터 좌표별 블록의 높이) 중 최솟값(최소 블록 높이)와 최댓값(최대 블록 높이)를 구한다.
2. 최소 블록 높이부터 최대 블록 높이까지 각각의 값으로 블록의 높이를 모두 일정하게 바꾸고(땅 고르기) 이 경우의 소요 시간과 블록 높이를 구한다.
3. 각각의 값으로 순차적으로 땅 고르기 작업을 할 때마다 낮은 시간을 우선적으로 산출하고 시간이 동일할 경우 더 높은 블록의 높이를 산출한다.(땅 고르기 작업 시 인벤토리가 부족한 경우는 고려하지 않는다.)

 

우선 입력받은 2차원 배열 상 요소값 중 최솟값과 최댓값을 구했는데, 이는 땅 고르기 작업 시 기준이 되는 값들이기 때문입니다. 땅 고르기 작업을 할 때 블록의 높이는 이 최솟값과 최댓값 사이의 범위를 넘어설 수는 없습니다. 왜냐하면 그 이상 블록을 제거하거나 블록을 쌓는 것은 '낭비'이기 때문인데, 이는 문제에서 요구하는 것은 ‘땅 고르기’ 작업에 걸리는 최소 시간이기 때문입니다.

 

이후 최솟값부터 최댓값까지 각각의 값(블록의 높이)별로 2차원 배열을 순회하면서 해당 블록의 높이만큼 블록을 제거하거나 쌓아주었습니다. 이때 제거 및 쌓기 행위별로 시간(time)과 인벤토리(inventory)를 카운팅(counting) 해주었고 인벤토리가 음수가 됐다는 것은 애초에 불가능한 작업이므로 이 경우는 별도로 고려하지 않았습니다.

 

매번 땅 고르기 작업을 완료할 때마다 최소 시간을 갱신하고 해당 블록 높이를 구했습니다. 이때 앞서 구한 시간과 현재 구한 시간이 동일한 경우 더 높은 블록의 높이를 산출하도록 했습니다. 최종적으로 모든 땅 고르기 작업이 완료되면 산출한 (최소) 작업 시간 값과 해당 블록 높이 값을 구할 수 있습니다.

 

 

소스 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

class Main {

    static int n, m, b;
    static int[][] map;

    static class Result {
        int time;
        int height;

        Result(int time, int height) {
            this.time = time;
            this.height = height;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st1 = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st1.nextToken());
        m = Integer.parseInt(st1.nextToken());
        b = Integer.parseInt(st1.nextToken());

        map = new int[n][m];

        StringTokenizer st2;

        for (int i = 0; i < n; i++) {
            st2 = new StringTokenizer(br.readLine());
            for (int j = 0; j < m; j++) {
                map[i][j] = Integer.parseInt(st2.nextToken());
            }
        }

        int min = 257;
        int max = -1;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                min = min > map[i][j] ? map[i][j] : min;
                max = map[i][j] > max ? map[i][j] : max;
            }
        }

        double result_time = Double.POSITIVE_INFINITY;
        int result_height = 0;

        for (int i = min; i < max + 1; i++) {
            Result result = operate(i);
            if (result != null) {
                result_time = result_time > result.time ? result.time : result_time;
                if (result_time == result.time) {
                    result_height = i > result_height ? i : result_height;
                }
            }
        }

        System.out.printf("%d %d", (int) result_time, result_height);
    }

    public static Result operate(int target) {
        int time = 0;
        int inventory = b;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (target > map[i][j]) {
                    inventory -= target - map[i][j];
                    time += target - map[i][j];
                }
                if (target < map[i][j]) {
                    time += 2*(map[i][j] - target);
                    inventory += map[i][j] - target;
                }
            }
        }
        if (inventory < 0) {
            return null;
        }

        return new Result(time, target);
    }
}

 

 

참고자료

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