[백준] 마인크래프트 JAVA

반응형

728x90

[백준] 마인크래프트

---

접근

• 브루트 포스 (Brute Force)

---

풀이

땅을 가장 높게 평탄화시키는 데 걸리는 시간과 땅의 높이를 구하는 문제이다. 블록을 쌓고 제거하여 모든 블록을 같은 높이로 만드는 데 걸리는 시간을 구해야 하는데 문제의 조건중 답이 여러 개 라면 가장 높은 높이를 출력하라는 부분이 있다.그 말은 블록의 높이가 다양하게 있을 때 땅을 모두 8의 높이로 평탄화할 때와 10의 높이로 평탄화할 때 걸리는 시간이 같을 수 있다는 소리다. 그렇다면 완전 탐색을 통해 모든 경우의 수를 구한 뒤 작업 시간이 최소이고 땅의 높이가 최대인 경우를 찾아야 한다.

 

일단 기본적으로 입력 값들을 받아 현재 땅의 최소 높이와 최대 높이를 구해줘야 한다. 그리고 최소 높이 부터 최대 높이까지 높이마다 반복을 진행하며 평탄화시켰을 때 걸리는 시간과 높이를 구한다.

int[][] land = new int[N][M];
int minHeight = 256, maxHeight = 0;

for (int i = 0; i < N; i++) {
	String[] col = br.readLine().split(" ");
	for (int j = 0; j < M; j++) {
		land[i][j] = Integer.parseInt(col[j]);
		minHeight = Math.min(minHeight, land[i][j]);
		maxHeight = Math.max(maxHeight, land[i][j]);
	}
}

입력받는 값들을 땅 배열에 넣어주며 최대 높이와 최소 높이를 구해준다. 최소 높이와 최대 높이는 문제에 주어지는 최댓값과 최솟값으로 초기화 시켜줬다.

int resultTime = Integer.MAX_VALUE;
int resultHeight = 0;

for (int height = minHeight; height <= maxHeight; height++) {
	int time = 0;
	int inventory = B;

반복이 시작되는 부분으로 결과를 담을 변수들을 초기화해줬고 반복문은 최소 높이부터 최대 높이까지 한 층씩 반복하여 진행된다. 반복문 아래 time 변수는 해당 층을 평탄화하는 데 걸리는 시간을 담을 변수이고 inventory 변수는 인벤토리에 들어있는 블록의 개수를 저장할 변수이다.

for (int i = 0; i < N; i++) {
	for (int j = 0; j < M; j++) {
		int diff = land[i][j] - height;
		if (diff > 0) {
			time += diff * 2;
			inventory += diff;
		} else if (diff < 0) {
			time -= diff;
			inventory += diff;
		}
	}
}

핵심 로직이 시작되는 부분이다. 우선 땅을 순회하며 해당 계층의 높이를 뺀다. 해당 계층과 높이가 같을 경우 작업이 필요하지 않고 땅이 해당 계층보다 높다면 인벤토리에 블록을 넣는 작업을 실행한다. 인벤토리에 넣는 작업은 2초의 시간을 소요하게 된다. 땅이 해당 계층보다 낮다면 인벤토리의 블록을 꺼내서 쌓아주는 작업을 하게 되는데 땅이 더 낮을 경우 diff의 변수 값은 이미 음수인 상태이므로 시간을 추가해 주기 위해선 뺄셈을 해주어야 하고 1초의 시간을 소요한다. 인벤토리에 블록을 빼주는 과정도 마찬가지로 이미 diff의 변수값이 음수인 상태이기 때문에 바로 인벤토리에 더하게 되면 사용한 만큼의 블록이 빼지게 된다.

if (inventory >= 0 && time <= resultTime) {
	resultTime = time;
	resultHeight = height;
}

마지막으로 층마다 값을 비교하여 주는 작업이다. 조건에 만족하기 위해선 인벤토리의 값이 음수여선 안되고 걸린 시간이 더 짧아야 한다.

---

전체 코드

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));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        String[] NMB = br.readLine().split(" ");

        int N = Integer.parseInt(NMB[0]);
        int M = Integer.parseInt(NMB[1]);
        int B = Integer.parseInt(NMB[2]);

        int[][] land = new int[N][M];
        int minHeight = 256, maxHeight = 0;

        for (int i = 0; i < N; i++) {
            String[] col = br.readLine().split(" ");
            for (int j = 0; j < M; j++) {
                land[i][j] = Integer.parseInt(col[j]);
                minHeight = Math.min(minHeight, land[i][j]);
                maxHeight = Math.max(maxHeight, land[i][j]);
            }
        }

        int resultTime = Integer.MAX_VALUE;
        int resultHeight = 0;

        for (int height = minHeight; height <= maxHeight; height++) {
            int time = 0;
            int inventory = B;

            for (int i = 0; i < N; i++) {
                for (int j = 0; j < M; j++) {
                    int diff = land[i][j] - height;
                    if (diff > 0) {
                        time += diff * 2;
                        inventory += diff;
                    } else if (diff < 0) {
                        time -= diff;
                        inventory += diff;
                    }
                }
            }

            if (inventory >= 0 && time <= resultTime) {
                resultTime = time;
                resultHeight = height;
            }
        }

        bw.write(String.valueOf(resultTime) + " " + String.valueOf(resultHeight));
        bw.flush();
        bw.close();
        br.close();
    }
}