JAVA - [백준]18111 - 마인크래프

출처

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

문제

인벤토리에 가지고 있는 제한된 숫자의 블록을 가지고, 땅을 블록으로 메꾸거나 블록을 캐서 땅을 고르게 만드는 문제이다.

접근 방법

문제를 보면, 생각보다 땅의 크기가 작아 경우의 수가 작을 것 이라고 생각 하기도 하였고, 모든 땅을 일정한 높이로 만들어야 하기 때문에 백트래킹이나 그래프 알고리즘으로는 해결할 수 없다고 생각하였다.

그렇기에 직접 모든 높이 경우의 수에 대해 시간을 구하고, 그 중 최소값을 구하는 방식으로 해결해보려고 하였다.

풀이

처음에는, 주어진 땅의 높이 중 하나라고 생각하였다. 예를 들어 1 x 2 땅에 [10, 5] 높이가 주어졌다면 10과 5 둘 중 하나의 높이에만 맞추도록 하여 함수에서 배열을 순회하였다.

하지만, 10과 5 둘중 하나의 높이가 아닌, 중간에 있는 높이도 얼마든지 될 수 있다는 사실을 간과하였다. 따라서 5와 10 중간에 있는 모든 경우의 수인 [5,6,7,8,9,10] 대해 탐색을 진행하도록 하였다.

이 외에도 여러가지 이유들 때문에 쉽사리 테스트 케이스가 통과하지 못하였는데, 내가 겪은 여러가지 반례들은 다음과 같았다.

• 최대 높이인 256을 포함하지 않아서 ( '<='을 사용 하지 않음)
• 맨 처음 주어진 땅의 높이가 고른 상태라면, 0 0 출력
• 1 1 0 과 0 이 주어지면 0 0 출력
• 배열을 처음부터 순서대로 깎고 놓으며 높이를 맞추는 것이 아닌, 한번 쭉 깎아 인벤토리에 블럭을 채우고 그 다음 블럭을 놓도록 해야함 (뒤에 블럭 수급이 많지만 앞에서 부족하여 반복문 탈출하는 경우 발생)
• BufferWriter를 활용하여 출력하였는데, 뒤에 개행을 하지 않음

개인적으로 어렵지는 않았지만 오랜만에 코딩테스트 문제를 풀어서 그런지 예외 처리나 반례 찾는게 너무 오래걸렸던 문제였던 것 같다.

코드

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

public class Main {
	static int N, M, B;
	static int[][] world;
	static List<Result> results;
	static int MAX_HEIGHT = 256;
	static int minh, maxh;

    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());

		world = new int[N][M];
		results = new ArrayList<>();
		maxh = 0;
		minh = 256;
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			for (int j = 0; j < M; j++) {
				world[i][j] = Integer.parseInt(st.nextToken());
				maxh = Math.max(maxh, world[i][j]);
				minh = Math.min(minh, world[i][j]);
			}
		}

		calcurate();
		
		int minTime = Integer.MAX_VALUE;
		int maxHeight = 0;
		for (Result result : results) {
			if (result.time < minTime) {
				minTime = result.time;
				maxHeight = result.height;
			} else if (result.time == minTime) {
				maxHeight = Math.max(maxHeight, result.height);
			}
		}

		if (minTime == Integer.MAX_VALUE) {
			minTime = 0;
		}
		if (minh == maxh) {
			maxHeight = minh;
		}

		bw.write(minTime + " " + maxHeight + "\n");

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

	public static void calcurate() {
		for (int h = minh; h <= maxh; h++) {
			int currentBlock = B;
			int time = 0;
			// 먼저 블록 깎아 인벤토리 채우기
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < M; j++) {
					if (world[i][j] > h) {
						currentBlock += (world[i][j] - h);
						time += (world[i][j] - h)*2;
					}
				}
			}

			// 블록 놓기
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < M; j++) {
					if (world[i][j] < h) {
						if (isPuttable(h - world[i][j], currentBlock)) {
							currentBlock -= (h - world[i][j]);
							time += h - world[i][j];
						} else {
							time = -1;
							break;
						}
					}
				}
				if (time < 0) {
					time = 0;
					break;
				}
			}
			if (time > 0) {
				results.add(new Result(time,h));
			}
		}
		
	}

	public static boolean isPuttable(int x, int y) {
		return x <= y && y > 0;
	}
}

class Result{
	int time;
	int height;

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