1. Problem 📃

[ 마인크래프트 ]

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

[ 문제 ]

팀 레드시프트는 대회 준비를 하다가 지루해져서 샌드박스 게임인 ‘마인크래프트’를 켰다.
마인크래프트는 1 × 1 × 1(세로, 가로, 높이) 크기의 블록들로 이루어진 3차원 세계에서 자유롭게 땅을 파거나 집을 지을 수 있는 게임이다.

목재를 충분히 모은 lvalue는 집을 짓기로 하였다.
하지만 고르지 않은 땅에는 집을 지을 수 없기 때문에 땅의 높이를 모두 동일하게 만드는 ‘땅 고르기’ 작업을 해야 한다.

lvalue는 세로 N, 가로 M 크기의 집터를 골랐다.
집터 맨 왼쪽 위의 좌표는 (0, 0)이다.
우리의 목적은 이 집터 내의 땅의 높이를 일정하게 바꾸는 것이다.
우리는 다음과 같은 두 종류의 작업을 할 수 있다.

1. 좌표 (i, j)의 가장 위에 있는 블록을 제거하여 인벤토리에 넣는다.
2. 인벤토리에서 블록 하나를 꺼내어 좌표 (i, j)의 가장 위에 있는 블록 위에 놓는다.

1번 작업은 2초가 걸리며, 2번 작업은 1초가 걸린다.
밤에는 무서운 몬스터들이 나오기 때문에 최대한 빨리 땅 고르기 작업을 마쳐야 한다.
‘땅 고르기’ 작업에 걸리는 최소 시간과 그 경우 땅의 높이를 출력하시오.

단, 집터 아래에 동굴 등 빈 공간은 존재하지 않으며, 집터 바깥에서 블록을 가져올 수 없다.
또한, 작업을 시작할 때 인벤토리에는 B개의 블록이 들어 있다.
땅의 높이는 256블록을 초과할 수 없으며, 음수가 될 수 없다.

2. Input ⌨️

[ 입력 ]

첫째 줄에 N, M, B가 주어진다. (1 ≤ M, N ≤ 500, 0 ≤ B ≤ 6.4 × 107)

둘째 줄부터 N개의 줄에 각각 M개의 정수로 땅의 높이가 주어진다.
(i + 2)번째 줄의 (j + 1)번째 수는 좌표 (i, j)에서의 땅의 높이를 나타낸다.
땅의 높이는 256보다 작거나 같은 자연수 또는 0이다.

3. Output 🖨

[ 출력 ]

첫째 줄에 땅을 고르는 데 걸리는 시간과 땅의 높이를 출력하시오.
답이 여러 개 있다면 그중에서 땅의 높이가 가장 높은 것을 출력하시오.

4. Example 📚

[ 입출력 예시 ]

5. Solution 🔑

아느 ㄴ형이 못 풀었다해서 걱정하면서 문제에 접근했던 것 같다.
문제를 풀 즈음에 조카집으로 조카를 보러가서 조카를 보면서 문제에 어떻게 접근할지 2일 정도 생각해보고 풀었더니 한 번에 풀 수 있었다.


1. 가로 세로 길이(N, M)을 선언하고 가지고 있는 블럭의 개수의 변수(B)를 선언하여 값을 입력받는다.


2. 길이를 입력 받은 만큼 배열 변수(land)를 설정해준다.
(상관없지만 나는 이중포문을 돌리기 싫어서 그냥 땅 모양을 일직선으로 만들어주었다.)


3. 그 다음 땅 한 칸마다의 블럭의 개수(높이)를 받아주면서 가장 큰 값과 가장 작은 값을 구분하기 위한 변수(max, min)을 선언해주고 땅의 최대 높이는 256이므로 min에는 256값으로 초기화하여 선언해주었다.
값들을 입력 받으며 가장 높은 땅과 가장 낮은 땅의 높이를 max, min값에 각각 담아준다.


4. 결국 땅의 높이의 범위는 min ~ max의 범위로 나타내어진다.
땅을 고르게 만들 수 있다면 몇 초가 걸리는지, 제일 짧으면서 제일 높은 층은 몇 층인지 알아내기 위해 범위 내의 값들을 하나씩 검사하여 답을 도출해낸다.


5. 내 인벤토리에 주어지는 블럭의 개수(inven), 높이가 부족한 칸에 대해 몇 개의 블럭이 더 필요한지에 대한 변수(need), 몇 초가 걸렸는지에 대한 변수(time)를 inven은 입력받은 값 B를, need와 time은 0으로 초기화하여 매 칸마다 이를 초기화 해준다.
가장 높고, 가장 빠른 높은 층을 만들기 위해서 max값부터 min값으로 확인해줬다.


6. 기준이 되는(min ~ max) 값을 기준으로 땅의 높이가 높다면 인벤토리(inven)에 깎은 블럭이 찰 것이므로, inven에 높이 차이 만큼을 추가해준다. 또 깎는 행동은 2초가 걸리기 때문에 블럭의 차이 * 2를 해서 걸린 시간을 계산해준다.
땅의 높이가 낮다면, need에 몇 개의 블럭이 필요한지, 그리고 설치하는 행동은 1초가 걸리기 때문에 블럭의 높이 차이만큼 시간 time에 더해주면된다. 같다면 continue다음 칸의 땅을 계산한다.


7. 필요한 블럭의 개수(need)가 내가 가진 블럭의 개수(inven)보다 작으면, 충분히 땅을 메울 수 있는 조건이므로 가장 빠른 시간(bestTime)과 가장 높은 층(maxFloor)을 담고, 도출된 시간은 애초의 시간과 비교하여 빠른지 확인한다.


8. 이렇게해서 나온 가장 빠른 시간(bestTime)과 가장 큰 층(maxFloor)을 출력문으로 출력한다.

6. Code 💻

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

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[] land = new int[N*M];
		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++) {
				land[M*i+j] = Integer.parseInt(st.nextToken());
				max = Math.max(max, land[M*i+j]);
				min = Math.min(min, land[M*i+j]);
			}
		}
//		System.out.println(max);
//		System.out.println(min);
		
		int time = 0;
		int inven = B;
		int need = 0;
		int bestTime = Integer.MAX_VALUE;
		int maxFloor = 0;
		
		for(int i=max; i>=min; i--) {

			inven = B;
			need = 0;
			time = 0;
			
//			System.out.println("목표 층 : " + i);
		
			for(int j=0; j<land.length; j++) {
				if(land[j] > i) {

					inven += land[j] - i;
					time += 2 * (land[j] - i);
				}
				else if(land[j] < i) {
					need += i - land[j];
					time += i - land[j];
				}
				else {
					continue;
				}
			}
//			System.out.println(i + " " + need);
			if(need <= inven) {
				if(time < bestTime) {
					maxFloor = i;
				}
				bestTime = Math.min(time, bestTime);
			}
			else {
				continue;
			}

		}
		
		System.out.println(bestTime + " " + maxFloor);
	}

}