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

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

18111번: 마인크래프트

소스 코드 : 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>

using namespace std;

int main()
{
	ios_base::sync_with_stdio(0);cin.tie(0);
	int N, M, B;
	int arr[500][500];
	int least_time = 987654321;
	int H;
	cin >> N >> M >> B;
	for (int i = 0;i < N;i++)
		for (int j = 0;j < M;j++)
			cin >> arr[i][j];

	for (int h = 0;h <= 256;h++)
	{
		int build = 0;
		int remove = 0;
		for (int i = 0;i < N;i++)
		{
			for (int j = 0;j < M;j++)
			{
				int height = arr[i][j] - h;
				if (height > 0) remove += height;
				else if (height < 0) build -= height;
			}
		}

		if (remove + B >= build)
		{
			int time = remove * 2 + build;
			if (least_time >= time)
			{
				least_time = time;
				H = h;
			}
		}
	}
	cout << least_time << ' ' << H << '\n';
}

마무리 : 문제를 보고 처음에 해결 방법이 떠오르지 않았다. 땅의 높이를 맞추는 것이 문제였는데 브루트포스 알고리즘으로 땅의 높이를 맞추고 제거하고나 쌓아서 최소의 시간을 찾는다.

 시간 제한이 1초이기 때문에 브루트포스 알고리즘을 사용하면 시간이 오래 걸릴것 같았지만 입력된 수가 많이 크지 않으니까 가능했던 문제였다.