[백준] 18111번 마인크래프트 C++ 코드

코드

#include <iostream>

using namespace std;
const int INF = 987654321;
int n,m,b, a[503][503], res = INF, max_h = -1, min_h = 257,oh;

// 높이 0 ~ 256, 칸의 크기 500*500
// 브루트포스로 풀 수 있을 듯
// 땅 높이 가장 높은 거, 낮은 거 계산
// 그 사이에 높이를 설정하고, 낮으면 더하고 높으면 깎기
// 다 돌렸는데 블록이 음수로 나오면 적용 X

void go() {
	int tmp = min_h;
    // 최저점부터 탐색
	while(tmp != (max_h + 1)) {
		int blockcnt = b; // 블록의 개수
		int tmptime = 0; // 걸린 시간
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < m; j++) { // 2번 작업
				if(tmp > a[i][j]) {
					tmptime += (tmp - a[i][j]);
					blockcnt -= tmp - a[i][j];
				} else if(tmp < a[i][j]) { // 1번 작업
					blockcnt += a[i][j] - tmp;
					tmptime += (a[i][j] - tmp)*2;
				}
			}
		}
        // 블록의 개수는 양수여야 한다
        if(blockcnt >= 0 && (res >= tmptime)) {
			res = tmptime;
			oh = tmp;
		}     
		tmp++; // 높이 증가시켜서 탐색
	}
}

void FASTIO() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
}

int main() {
	FASTIO();
	cin >> n >> m >> b;
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < m; j++) {
			cin >> a[i][j];
			max_h = max(max_h, a[i][j]);
			min_h = min(min_h, a[i][j]);
		}
	}
	go();
	cout << res << " " << oh << '\n';
	return 0;
}

풀이

높이가 0에서 256이고, 땅의 크기가 500*500이라서 모든 경우를 탐색해도 충분히 해결할 수 있을 거라 생각했다. 최저 높이와 최대 높이를 찾아주고 그 사이에서 높이를 높여가며 땅 고르기를 하는 데 가장 적은 시간을 찾을 수 있다. 주의할 것은 블록의 개수가 음수면 적용이 안된다는 것과 답이 여러 개 있다면 땅의 높이가 가장 높은 것을 고르라는 조건이다. 이는 부등호를 이용하면 쉽게 해결할 수 있다.