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

문제 링크: https://www.acmicpc.net/problem/18111

 

깎거나, 쌓거나 둘 중 하나를 하면 됩니다.

깎는데는 2초, 쌓는데는 1초가 걸리니까 최대한 쌓는 방향으로 하면 되겠죠.

그런데 인벤토리에 있는 블록 수가 주어지고 이 블록만큼만 사용해 쌓을 수 있습니다.

[최소높이, 최대높이]로 모든 높이에 대해 쌓거나 깎거나 할 수 있는 경우에만 <걸린시간, 높이>를 저장해서 가장 적게 걸린 시간 중 가장 높은 것을 갖고오면 됩니다. 즉 브루트포스죠

 

유의할 점은 깎은 블록을 쌓는 데 쓸 수 있다는 점이 있겠습니다.

// 18111

#pragma GCC optimize ("Ofast")

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;


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


int cost(int from, int to) {
	if (from < to)	// 쌓기
		return to - from;
	else	// 부수기
		return 2 * (from - to);
}

// 가능한 경우, 걸리는 시간 반환
// 불가능한 경우, -1
int possible(int target_height, int blocks) {
	int elapsed_time = 0;
	int needed_blocks = 0;

	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j) {
			elapsed_time += cost(plane[i][j], target_height);
			needed_blocks += target_height - plane[i][j];
		}
	}

	return (needed_blocks <= blocks ? elapsed_time : -1);
}

int main()
{
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
#endif

	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	cin >> n >> m >> b;

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

	vector<pair<int, int>> ans;
	for (int i = 0; i <= max_height; ++i) {
		int p = possible(i, b);
		if (p != -1) {
			ans.emplace_back(p, -i);
		}
	}
	sort(ans.begin(), ans.end());

	cout << ans[0].first << ' ' << -ans[0].second << '\n';

	return 0;
}

지금 보니 구현이 좀 비효율적이네요. 그래도 입력 크기가 작아 푸는데 문제는 없습니다