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

---

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

---

📌 문제

문제 유형

• 구현
• 브루트포스 알고리즘

문제 설명

땅을 고르게 만들기 위해 다음과 같은 두 가지 작업을 수행할 수 있다.

1. 좌표 (i, j)의 가장 위에 있는 블록을 제거하여 인벤토리에 넣는다. → 2초 소요
2. 인벤토리에서 블록 하나를 꺼내어 좌표 (i, j)의 가장 위에 있는 블록 위에 놓는다. → 1초 소요

• 집터는 세로 N, 가로 M 크기이며, 집터 맨 왼쪽 위의 좌표는 (0, 0)
• 작업을 시작할 때 인벤토리에는 B개의 블록이 들어 있다.
• 목표는 “땅을 모두 같은 높이로 맞추는 데 걸리는 최소 시간”을 구하는 것.
• 가능한 경우가 여러 개라면, 더 높은 높이를 선택한다.

입력

3 4 99
0 0 0 0
0 0 0 0
0 0 0 1

출력

2 0

🔍 문제 풀이

모든 높이 h를 시도하면서 해당 높이로 땅을 일정히 고르게 할 수 있는지, 걸리는 시간을 계산해보고,

그 중 최소 시간 + 가장 높은 높이를 선택하면 되는 문제이다.

1. ground 배열에서 최솟값(minHeight), 최댓값(maxHeight) 계산
2. 가능한 모든 높이를 반복
3. 각 칸의 현재 높이와 h를 비교해:
   • 높이가 더 높으면 → 블록 제거 (remove += diff)
   • 낮으면 → 블록 설치 (create -= diff)
4. 인벤토리 블록으로 설치가 가능한지 확인: remove + b >= create
5. 가능하다면 시간 계산: time = remove * 2 + create
6. 조건 비교 후 최적 높이 및 시간 출력

📌 놓친 점

초기 접근 방식

처음엔 최댓값/최솟값 개수 비교로 접근함

• 더 적은 쪽을 기준으로 블록 설치 or 제거 시도

• time += 1 또는 *2로 단순 계산하려 함

• 하지만,
  • 땅 높이는 2개뿐 아니라 여러 값이 섞여 있을 수 있고,
  • 모든 칸을 동일한 높이로 만드는 문제이므로,
  • 모든 높이(h)를 직접 시뮬레이션하는 방식이 필요했음
  • 결국, 검색의 힘을 빌려 브루트포스로 풀어야 한다는 것을 꺠달음

조건 누락

처음엔 시간 비교만 하고, 높이가 같은 경우 더 높은 쪽을 선택한다는 조건을 놓침

if (time < minTime) {
    ...
}

하지만, time이 같다면 h가 더 큰 쪽을 선택해야 하므로

if (time < minTime || (time == minTime && h > resultHeight)) {

처럼 조건을 두 가지로 구성해야 했음

💻 전체 코드

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[][] ground = new int[n][m];

        int maxHeight = Integer.MIN_VALUE;
        int minHeight = Integer.MAX_VALUE;

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < m; j++) {
                ground[i][j] = Integer.parseInt(st.nextToken());
                maxHeight = Math.max(maxHeight, ground[i][j]);
                minHeight = Math.min(minHeight, ground[i][j]);
            }
        }

        int minTime = Integer.MAX_VALUE;
        int resultHeight = 0;
        for(int h = minHeight; h <= maxHeight; h++){
            int remove = 0;
            int create = 0;

            for(int i=0; i<n; i++){
                for(int j=0; j<m; j++){
                    int diff = ground[i][j] - h; // 현재 높이(ground[i][j])와 목표 높이(h)의 차이값(diff)

                    if(diff < 0){
                        create -= diff;
                    }else{
                        remove += diff;
                    }
                }
            }

            if(remove + b >= create){
                int time = remove * 2 + create;

                if(time < minTime || (time == minTime && h > resultHeight)){
                    minTime = time;
                    resultHeight = h;
                }
            }
        }


        System.out.println(minTime + " " + resultHeight);


    }
}