[백준 18111번 / Java] 마인크래프트

문제 링크

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

18111번: 마인크래프트

 

 

 

풀이

단순 브루트 포스로 다 때려박아서 구했다.

 

문제에서 시간제한과 메모리 크기가 주어졌고, 메모리 크기가 가장 클 것으로 예상되는 minecraft 배열은 최대 크기가 500*500의 int 배열이며, 이는 500*500*4로 최대 1,000,000바이트의 메모리를 차지한다. 계산기를 두드려보니 0.95MB 정도 차지하는 것 같다. 나머지 코드들은 파싱을 위한 변수 사용 등으로, 크게 메모리를 차지하는 부분이 없었다.

 

또한 시간적인 부분에서도, 최대 O(256*500^2)의 시간복잡도를 가지기 때문에, 가능할 것으로 판단하여 단순 반복문을 활용하여 풀어냈다.

 

문제에서 주의해야 할 부분은 블록이 음수일 경우는 제외하고, 같은 시간이 걸릴 경우 최대한 높은 값을 출력해야 한다는 것이었다. 문제 조건만 잘 파악한다면 쉽게 풀 수 있는 문제였다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

import java.util.*;

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 min = Integer.MAX_VALUE;
		int max = -1;
		for(int i=0; i<N; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			for(int j=0; j<M; j++) {
				minecraft[i][j] = Integer.parseInt(st.nextToken());
				min = Math.min(min, minecraft[i][j]);
				max = Math.max(max, minecraft[i][j]);
			}
		}
		
		int min_sec = Integer.MAX_VALUE;
		int high_block = 0;
		for(int i=min; i<=max; i++) {
			int second = 0;
			int block = B;
			
			for(int j=0; j<N; j++) {
				for(int k=0; k<M; k++) {
					if(i > minecraft[j][k]) {
						second += i-minecraft[j][k];
						block -= i-minecraft[j][k];
					}
					else if(i < minecraft[j][k]) {
						second += (minecraft[j][k]-i)*2;
						block += minecraft[j][k]-i;
					}
				}
			}
			if(block < 0) continue;
			
			if(min_sec >= second) {
				min_sec = second;
				high_block = Math.max(high_block, i);
			}
		}
		
		System.out.println(min_sec + " " + high_block);		
	}
}