[CLASS 3: 브루트포스] 백준 18111 마인크래프트

18111번: 마인크래프트

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

 

 # 코드

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int b = Integer.parseInt(st.nextToken());
        int[][] arr = new int[n][m];

        int maxHeight = 0;
        int minHeight = 256;

        // 입력을 받음과 동시에 최대/최소 높이를 저장함
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for (int j = 0; j < m; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
                maxHeight = Math.max(maxHeight, arr[i][j]);
                minHeight = Math.min(minHeight, arr[i][j]);
            }
        }

        int min_sec = Integer.MAX_VALUE; // 최소 시간
        int optimal_height = 0; // 땅의 높이

        // minHeight ~ maxHeight 범위 내에서만 탐색
        for (int h = minHeight; h <= maxHeight; h++) {
            int sec = 0; // 현재 목표 높이 h로 맞추기 위해 걸리는 시간
            int inven = b; // 인벤토리에 들어있는 블록

            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    int gap = arr[i][j] - h;

                    if (gap > 0) { // 블록을 제거해야 하는 경우
                        sec += gap * 2;
                        inven += gap;
                    } else if (gap < 0) { // 블록을 추가해야 하는 경우
                        sec -= gap; // gap이 음수이므로 -gap으로 더함
                        inven += gap; // 인벤토리에서 블록 차감
                    }
                }
            }

            // 인벤토리에 남은 블록이 음수이면 건너뜀
            if (inven < 0) continue;

            // 최소 시간이거나, 같은 시간이라면 더 높은 높이로 갱신
            if (min_sec >= sec) {
                min_sec = sec;
                optimal_height = h;
            }
        }

        System.out.println(min_sec + " " + optimal_height);
        br.close();
    }
}

• 해당 문제는 브루트포스 알고리즘으로 가능한 모든 경우의 수를 검사하고 가장 최적의 값을 출력하는 문제였다.
• 천천히 풀어보면 어려울 것은 없겠으나, 아래 한 가지 경우만 주의하면 될 것 같다.
• 블록을 추가해야 하는 경우 인벤토리가 음수가 되더라도 (다른 좌표에서 보충할 수도 있으므로) 일단 추가하고, 목표 높이로 맞춰놓은 이후에 최종으로 인벤토리를 확인해야 한다는 점이다.
• 땅을 고르는 순서가 정해져있지 않기 때문에 다른 좌표에서 제거한 블록을 사용할 수 있다는 것만 유의해 풀면 되겠다.