[백준 - 18111번] 마인크래프트

•  탐색할 높이 범위를 가능한 줄이는게 중요함

#include <iostream>
#include <vector>
#include <map>

using namespace std;

int main(void)
{
	int N, M, B;
	cin >> N >> M >> B;

	// 땅 높이 입력
	vector<vector<int>> v;
	int total_block = 0;
	int n;
	int maxh = 0;
	int minh = 257;

	for (int i = 0; i < N; i++)
	{
		vector<int> v2;
		for (int j = 0; j < M; j++)
		{
			cin >> n;
			maxh = maxh < n ? n : maxh;
			minh = minh > n ? n : minh;
			v2.push_back(n);
			total_block += n;
		}
		v.push_back(v2);
	}

	// 최소 시간과 그 경우 땅의 높이를 출력
	// 땅의 높이가 가장 높은 것을 출력

	// 가지고 있는 블럭으로 가능한 최대 높이
	int max_height = (total_block + B) / (N * M);
	maxh = maxh > max_height ? max_height : maxh;

	map<int, int> time_height_m;
	int spot_h, time;


	for (int h = minh; h <= maxh; h++)
	{
		time = 0;
		for (int i = 0; i < N; i++)
		{
			for (int j = 0; j < M; j++)
			{
				spot_h = v[i][j];
				if (spot_h > h) time += (spot_h - h) * 2;
				else if (spot_h < h) time += (h - spot_h);
			}
		}
		if (time_height_m.find(time) == time_height_m.end())
		{
			time_height_m.insert(make_pair(time, h));
		}
		else
		{
			time_height_m.find(time)->second = time_height_m.find(time)->second > h ? time_height_m.find(time)->second : h;
		}
	}

	cout << time_height_m.begin()->first << " " << time_height_m.begin()->second;

	return 0;
}

 

[참고 자료]