[백준] 18111 마인크래프트 / 자바(Java)

문제

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

18111번: 마인크래프트

 

---

해설

높이 있는 블럭은 낮추고, 낮게 있는 블럭은 높여 평평하게 고르는데 필요한 최소한의 시간을 구하는 문제입니다.

 

일일히 하나씩 빼고 넣기에는 너무 구현이 복잡해 질 듯하여

높이의 제한이 256인 것을 보고 모든 높이를 대입해보자는 브루트포스 방식을 사용하기로 했습니다.

 

가로, 세로는 각각 500이므로 모든 높이에서의 시간을 확인해 보는데 256*500*500으로 계산해 볼만한 시간복잡도입니다.

 

그럼에도 범위를 최대한 좁히기 위해 입력을 받으며 블럭 높이의 최소높이와 최대높이를 저장합니다.

최소높이부터 최대높이를 순회하며 각 블럭을 특정 높이로 맞추는데 걸리는 시간의 총 합을 각각 구해 최소값을 찾습니다.

 

이때 중간값부터 시작하면 더 최소값을 빨리 구할 가능성이 있어 중간에서부터 최대로, 중간에서 부터 최소로 구하며 이미 구한 최소값보다 값이 커지면 지금 연산중인 높이를 중단하고 다음 높이를 탐색하는 방식으로 해결하면 더 좋습니다.

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main{
//34488	584
	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 min=Integer.MAX_VALUE,max=0;
		int land [] = new int [N*M];
		for(int i=0;i<N;i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0;j<M;j++) {
				land[i*M+j]=Integer.parseInt(st.nextToken());
				if(land[i*M+j]>max) max = land[i*M+j];
				if(land[i*M+j]<min) min = land[i*M+j];
			}
		}
		int anstime=Integer.MAX_VALUE;
		int ansheight=-1;
		// 예상되는 목표 층수(입력의 최소와 최대 사이)
		for(int i=min;i<=max;i++) {
			boolean flag=false;
			int time = 0;
			int blocks = B;
			// 모든 위치마다 목표층수에 맞춰서 작업
			for(int j=0;j<land.length;j++) {
				int diff = land[j]-i;
				if(diff>0) {// 더 높을때(제거작업)
					time += Math.abs(diff)*2;
					blocks +=Math.abs(diff);
				}else if(diff<0){// 더 낮을때 (추가작업)
					time += Math.abs(diff);
					blocks -=Math.abs(diff);
				}
				if(time>anstime) {
					flag=true;
					break;
				}
			}
			if(flag)continue;
			// 가능하다고 시간이 전보다 효율적이라면
			if(blocks>=0&&time<=anstime) {
				anstime = time;
				ansheight=i;
			}
		}
		
		System.out.println(anstime+" "+ansheight);
	}
}