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

 

알고리즘 분류: 구현, 브루트포스 알고리즘

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

18111번: 마인크래프트

 

 

【 풀이 】

 

주어진 배열요소 모두를 일정한 높이로 만드는 데 걸리는 최소 시간과 땅의 높이를 구하는 문제이다.

이 문제는 브루트포스 알고리즘을 이용하여 생각보다 간단히 해결할 수 있다.

즉 3중 for 문으로, 첫 for문은 모든 높이의 경우에 대해서, 두번째/세번째 for문은 주어진 배열에서 검증하면 된다.

 

remove(배열 요소가 설정된 높이보다 높을 때 제거해야할 블록 개수)

stack(배열 요소가 설정된 높이보다 낮을 때 쌓아야 할 블록 개수) 두 변수를 설정하고

제거하고 얻어낸 블록 + 인벤토리에 있던 블록, 즉 remove + B 가 stack 보다 크거나 같으면

"제거할 블록 개수 * 2 + 쌓아야 할 블록 개수 = 시간" 이 된다.

그때 반복문에서 h가 최대 높이가 되는 것이다.

 

 

 

【 코드 】

 

#include<iostream>
using namespace std;

//	제거 2초
//	채우기 1초

int land[501][501];
int main(void)
{
	int mint = 99999999;
	int minh = 99999999;
	int time;
	int N, M, B;
	cin >> N >> M >> B;

	for (int i = 0; i < N; i++)
		for (int j = 0; j < M; j++)
			cin >> land[i][j];

	for (int h = 0; h <= 256; h++)
	{
		int remove = 0;
		int stack = 0;
		for (int i = 0; i < N; i++)
		{
			for (int j = 0; j < M; j++)
			{
				if (land[i][j] > h)		//	제거해야할 블록 개수
					remove += land[i][j] - h;
				else if (land[i][j] == h)		//	같으면 통과
					continue;
				else if (land[i][j] < h)		//	쌓아야 할 블록 개수
					stack += h - land[i][j];
			}
		}
		if (remove + B >= stack)		//	"제거해서 인벤토리에 추가한 블록 + 원래 있던 블록 >= 쌓아야할 블록 개수" 라면..
		{
			time = remove * 2 + stack;
			if (time <= mint)
			{
				mint = time;
				minh = h;		//	현재 설정된 높이가 최소높이가 됨
			}
		}
	}
	cout << mint << ' ' << minh;
	return 0;
}