백준 18111번 마인크래프트 - Java 구현

마인크래프트

 

문제를 요약하면

 

땅을 평평하게 하고 싶다.

N x M 크기의 맵이있고, 내 인벤토리엔 B 개수의 블럭이 주어진다.

맵의 숫자만큼의 높이로 블럭이 쌓여져 있고, 쌓는데 1초, 치우는데 2초가 걸린다.

블럭이 존재하지 않다면 더이상 사용할 수 없고, 블럭을 치우면 인벤토리에 들어오게 된다.

 

모든 땅의 높이가 같게하는 방법에서 가장 최단 시간을 구하고,

동시간대가 존재한다면 가장 높이 쌓은 높이를 출력하면 된다.

 

높이가 기본적으로 0부터 256까지이고 음수가 될수 없어 범위는 0 <= x <= 256 이다.

시간계산이기 때문에 임의의 높이 X를 정하고, X를 기준으로 시간을 계산해 주었다.
X보다 낮은 높이의 땅이라면 1 * (X - (현재 땅의 높이))

X보다 높은 높이의 땅이라면 2 * Math.abs(X - (현재 땅의 높이)) 만큼의 시간 소요된다.

 

블럭의 개수도 중요한데

가능한 높이려면 N * M * X 가 필요하고, 이는 B + input  총합이 되겠다.

 

마지막으로 최단시간을 구하고, 시간이 같다면 더 큰 높이로 갱신해주면 된다.

 

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[] MineCraft = new int[N * M];
        int blocks = B;
        int max = 0;
        int min = 256;
 
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < M; j++) {
                int height = Integer.parseInt(st.nextToken());
                MineCraft[i * M + j] = height;
                blocks += height;  // 전체 블록 개수 계산
                max = Math.max(max, height);
                min = Math.min(min, height);
            }
        }
 
        int maxHeight = min;  // 초기 높이는 최소값으로 설정
        int minTime = Integer.MAX_VALUE;
 
        for (int i = min; i <= max && i <= (blocks) / (N * M); i++) {
            int time = 0;
            for (int j = 0; j < N * M; j++) {
                int diff = MineCraft[j] - i;
 
                if (diff > 0) {
                    time += diff * 2;  // 블록 제거
                } else {
                    time -= diff;  // 블록 추가 , diff 는 음수
                }
            }
 
            if (time <= minTime) {  // 시간이 같은 경우 최대 높이로
                minTime = time;
                maxHeight = i;
            }
        }
 
        System.out.println(minTime + " " + maxHeight);
    }
}