[210703][백준/BOJ] 18111번 마인크래프트

문제

입출력

풀이

n과 m은 최대 500이며 땅의 높이는 최대 256이므로 500 x 500 x 256 = 6천 4백만 이므로
브루트포스 알고리즘으로 문제를 풀 수 있다.

1. 가능한 땅의 높이인 0부터 256까지 완전탐색을 한다.
2. 현재 위치가 땅보다 작다면 2번작업을 수행하며 현재 위치가 땅보다 크다면 1번작업을 수행한다.
3. 인벤토리에 남은 블록의 개수가 0 이상일때라는 조건이 없으면 인벤토리에 있는 블록 개수 이상으로 1번이나 2번작업을 수행해서 땅을 고르게 만들 수 있기 때문에 인벤토리가 0 이상일때라는 조건이 필요하다.
4. 인벤토리가 0이상 일때 걸리는 최소 시간과 높이를 구한다.

코드

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

int board[SIZE][SIZE];
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	int n, m, b;
	cin >> n >> m >> b;

	// 걸리는시간, 땅의 높이
	int minT = INT_MAX, maxH, tmp;

	for (int i = 0; i < n; ++i)
		for (int j = 0; j < m; ++j)
			cin >> board[i][j];

	// 최대 256 * 500 * 500이므로 브루트포스로 해결
	for (int i = 0; i <= 256; ++i)
	{
		// sum은 걸리는 시간, tmp는 인벤토리값을 저장
		int sum = 0, tmp = b;
		for (int j = 0; j < n; ++j)
		{
			for (int k = 0; k < m; ++k)
			{
				// i보다 작으면 2번작업 수행
				if (board[j][k] < i)
				{
					// 인벤토리에서 블록을 꺼냄 - 1초
					sum += i - board[j][k];
					tmp -= i - board[j][k];
				}
				// i보다 크면 1번작업 수행
				else if (board[j][k] > i)
				{
					// 인벤토리에 블록을 넣음 - 2초
					sum += (board[j][k] - i) * 2;
					tmp += board[j][k] - i;
				}
			}
		}
		// 인벤토리가 0보다 작으면 안됨
		// 이 조건이 없으면 인벤토리에 있는 블록의 개수 이상으로 
		// 블록을 사용해서 땅을 바로 고르게 만들 수 있음
		if (tmp >= 0)
		{
			if (sum <= minT)
			{
				minT = sum;
				maxH = i;
			}
		}
	}
	cout << minT << ' ' << maxH << '\n';
}