[백준/C++] 18111번: 마인크래프트

문제

설명

블럭을 쌓거나 제거해서 평평한 바닥을 만들면 되는 문제이다.

입력되는 땅의 높이가 0~256 사이라서 0과 256 사이의 높이를 모두 체크해도 되지만,

입력된 높이의 최소~최대 사이만 체크해도 가능하다.

답이 여러개라면 가장 땅의 높이가 높은 것을 출력해야 하기에 낮은 높이부터 체크하였다.

각 높이를 돌면서, 평평하게 만드는데 드는 시간과 블럭을 체크하였고, 블럭이 부족하다면 답으로 기록하지 않았다.

 

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <math.h>
#include <climits>
using namespace std;

int N, M, B;
int arr[500][500];
int answer_time = INT_MAX;
int answer_height;

int main() {

	cin >> N >> M >> B;

	int min = INT_MAX, max = INT_MIN;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> arr[i][j];
			if (arr[i][j] > max) max = arr[i][j];
			if (arr[i][j] < min) min = arr[i][j];
		}
	}

	for (int height = min; height <= max; height++) {
		int time = 0;
		int block = B;

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (arr[i][j] > height) {
					time += abs(arr[i][j] - height) * 2;
					block += abs(arr[i][j] - height);
				}
				else if (arr[i][j] < height) {
					time += abs(arr[i][j] - height);
					block -= abs(arr[i][j] - height);
				}
			}
		}

		if (answer_time >= time && block >= 0) {
			answer_time = time;
			answer_height = height;
		}

	}

	cout << answer_time << " " << answer_height;

	return 0;
}