백준 18111 : 마인크래프트

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

18111번: 마인크래프트

 

가로, 세로 500, 최대 높이가 256이므로 500 x 500 x 256 = 64,000,000 으로 브루트포스로 해결할 수 있는 문제다.

 

#include <iostream>

#define max(a,b) a>b?a:b
using namespace std;

int n, m, b;
int board[500][500];

void solution() {
	int height = 0;
	int cur_time, curb, min_time, min_height, req;
	bool flag;

	cin >> n >> m >> b;
	
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> board[i][j];
			height = max(height, board[i][j]);
		}
	}

	min_time = 1e9;
	while (height >= 0) {
		cur_time = 0, curb = b;

		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (board[i][j] <= height) continue;
				req = board[i][j] - height;
				cur_time += 2 * req;
				curb += req;
			}
		}

		flag = 0;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (board[i][j] >= height) continue;
				req = height - board[i][j];
				if (curb < req) { cur_time += 1e9; flag = 1; break; }
				cur_time += req;
				curb -= req;
			}
			if (flag) break;
		}

		if (cur_time < min_time) { 
			min_time = cur_time; min_height = height;
		}

		--height;
	}

	cout << min_time << ' ' << min_height << '\n';
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	solution();

	return 0;
}

메모리: 2996 kb

시간: 224 ms