백준[18111]번 : 마인크래프트 ( JAVA )

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

18111번: 마인크래프트

---

Code

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

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));
		
		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 max = -1;
		int min = 257;
		
		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 (arr[i][j] < min) {
					min = arr[i][j]; // 최소값
				}
				if (arr[i][j] > max) {
					max = arr[i][j]; // 최댓값
				}
			}
		}
		
		int ans = 99999999;
		int floor = -1;
		int B = b; // 블록 개수
		
		for(int t=max;t>=min;t--) {
			int time = 0;
		
			b = B; //b 초기화
			
			for(int i=0;i<n;i++) {
				for(int j=0;j<m;j++) {
					if(arr[i][j] < t) {
						time+= (t - arr[i][j]);
						b-=(t-arr[i][j]);
					}
					else if(arr[i][j] > t) {
						time+= (arr[i][j] - t) * 2;
						b+=(arr[i][j]-t);
					}
				}
			}
			
			if(b >= 0) {
				if(ans > time) {
					ans = time;
					floor = t;
				}
				else if(ans == time) {
					if(floor < t) {
						floor = t;
					}
				}
			}
		
		}
		
		bw.write(ans+" "+floor);
		
		br.close();
		bw.close();
	}
}

---

문제를 처음보고 시간을 최소로 해야겠다는 생각에 가장 많이 나온 블록의 수( 최빈값 )를 구해서 문제를 풀려고 했다.

계속 틀려서 문제 카테고리를 보니 부르트포스 알고리즘이 있어 다시 풀었다.

 

입력받은 블록의 수들의 최댓값과 최솟값을 구해서 그 사이에 있는 모든 블록의 수들의 경우를 구해서 최솟값을 구하는 방식으로 풀었다.

 

먼저, 블록을 쌓을 때 블록이 없으면 어떻게 해야 하나라는 생각은 뒤로 두고 

블록을 제거할 경우와 블록을 쌓을 경우의 시간과 블록의 수를 계산하여 저장했다.

 

그 후 블록의 수가 음수가 된다면, 블록이 부족해서 평평하게 만들지 못하므로 조건에 충족하지 못한다.

만약 음수가 아니라면,  시간이 최소일때와 시간이 같을 때의 경우를 나누어 저장해 준다.

 

입력받은 블록의 모든 경우를 탐색할 때 시간과 들고 있는 블록의 수를 초기화해 주는 것을 잊지 말아야 한다.