[백준] 18111번_마인크래프트(Java)

문제 풀이

백준의 18111번 문제입니다. 문제 출처

(1) 문제 파악

(2) 문제 풀이 방법 생각하기

땅의 높이를 모두 같게 만드려면 어느 높이로 같게 만들 것인지를 결정해야 합니다.

기준이 될 땅의 높이는 min, max 사이에 존재할 것이므로 min부터 max까지 순회하며 시간이 최소로 걸리는 땅의 최대 높이를 찾아내면 됩니다. (주의할 점은 인벤토리에 있는 블록이 없다면 더이상 땅을 채울 수 없다는 것입니다!)

(3) 시간 복잡도 확인

시간 제한은 1초 입니다. 즉, 대략 1억번 연산 안에 문제를 해결해야 합니다.

\[1 <= N, M <= 500\]

• 최대와 최소값을 구하는 연산: O(NM)
• 전체 지형을 순회하면서 최소 시간을 찾는 연산: O((max-min)*NM)

전체 지형을 순회하는 연산에서 시간이 많이 쓰이며 최악의 경우 약 64,000,000번의 연산을 수행하기에 시간 내에 문제를 해결할 수 있습니다.

(4) 구현

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[][] arr = new int[N][M];
		int min = 256;
		int max = 0;
		
		for(int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j = 0; j < M; j++) {
				arr[i][j] = Integer.parseInt(st.nextToken());
				if(min > arr[i][j]) min = arr[i][j];
				if(max < arr[i][j]) max = arr[i][j];
			}
		}

		int time = Integer.MAX_VALUE;
		int high = 0;
        
		for(int h = min; h <= max; h++) {
			int count = 0;
			int block = B;
			for(int j = 0; j < N; j++) {
				for(int k = 0; k < M; k++) {
					if(h < arr[j][k]) {
						count += ((arr[j][k] - h) * 2);
						block += (arr[j][k] - h);
					}else {
						count += (h - arr[j][k]);
						block -= (h - arr[j][k]);
					}
				}
			}

			if(block < 0) break;
			
			if(time >= count) {
				time = count;
				high = h;
			}
		}

		System.out.println(time + " " + high);
        br.close();
	}
}