[C++] BOJ 18111 마인크래프트

문제

백준 18111번

www.acmicpc.net/problem/18111

18111번: 마인크래프트

코드

#include<iostream>
#include<algorithm>
using namespace std;

int n, m, inven;
int min_time = 2147000000, res_height;

int arr[250000];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL); 
	cout.tie(NULL);

	cin >> n >> m >> inven;
	int size = n * m;
   
	for (int i = 0; i < size; i++) { //집터 상태 입력받음
		cin >> arr[i];
	}
	
	for (int h = 256; h >= 0; h--) {
		int place = 0, remove = 0; //놓아야 하는 블록 수: place, 제거해야 하는 블록 수: remove
		for (int i = 0; i < size; i++) {
        	if (arr[i] > h) remove += arr[i] - h;  //기준 높이 h보다 땅이 높으면 remove에 둘의 차를 더해준다
            else place += h - arr[i];  //기준 높이 h보다 땅이 낮으면 place에 둘의 차를 더해준다
		}
       
		if (remove + inven >= place) {
        	//인벤토리에 남은 블록이 없으면, 블록을 놓을 수가 없으므로 이 경우는 제외해준다
			int time = 2 * remove + place;
            
			if (min_time > time) {//최소시간을 갱신해준다
				min_time = time;
				res_height = h;
			}
		}
	}
	cout << min_time << ' ' << res_height;
}

풀이방법

for문을 이용해 높이 h값을 최대치인 256에서부터 감소시켜가며 각 높이 h에 맞춰서 땅을 편평화시킬 때 소요시간을 계산한다. 각 기준높이 h마다 제거해야 하는 블록 수 remove와 채워넣어야 하는 블록 수 place값을 구한 뒤, 이를 이용해 h높이에 맞춰 편평화시킬 떄 필요한 시간을 구한다. 단, 인벤토리에 있던 블록 수와 새로 제거해서 인벤토리에 추가한 블록 수의 합이 채워넣어야 하는 블록 수보다 작으면 편평화 작업을 완성할 수 없기 때문에, 이 경우에는 소요시간을 계산하지 않는다. 각 층마다 소요시간을 구하면, 최소시간과 그때의 h값을 갱신해준다. 

고민과정

for문을 돌릴 때, 높이 h값을 그냥 256에서 0까지 할지, min, max값을 구해놓고 그 구간에서만 돌릴지 고민했다.

각 층마다 편평화하는데 필요한 시간을 배열에 저장하려다가, 그럴 필요가 없다는 것을 깨닫고 수정했다.