[백준 BOJ18111] 마인크래프트 (C++)

1. 제목

- 백준 18111 마인크래프트

- BOJ 18111 마인크래프트

문제 링크 : 18111번: 마인크래프트 (acmicpc.net)

18111번: 마인크래프트

---

2. 풀이 과정

 

완전탐색으로 문제 해결을 했어요.

일단 먼저 최대 쌓을 수 있는 높이를 구한 다음 (최대높이 = 총 블룩개수 / (가로 * 세로)) 높이 0부터 최대 높이 까지 쌓아보며 작업시간을 구한 후 가장 낮은 작업시간을 가진 값을 구하는 식으로 구현했어요.

---

3. 코드

#include <iostream>

using namespace std;


int map[500][500];
int col, row, ownBlocks;
int totalBlockAmount, maxHeight;
int t = 99999999, height;

void Solution()
{
	// 최대 높이 구하기
	// 최대 높이 = 총블록갯수 / (가로 * 세로)
	maxHeight = totalBlockAmount / (col * row);

	for (int h = 0; h <= maxHeight; h++)
	{
		int currentTime = 0;

		for (int y = 0; y < col; y++)
		{
			for (int x = 0; x < row; x++)
			{
				// 현재 높이보다 크다면 땅을 판다.
				if (map[y][x] > h)				
					currentTime += ((map[y][x] - h) *2);				
				// 현재 높이보다 작다면 블록을 쌓는다.
				else if (map[y][x] < h)
					currentTime += (h - map[y][x]);				
			}
		}

		// 현재 작업시간이 최솟값 보다 작다면 갱신
		if (currentTime < t)
		{
			t = currentTime;
			height = h;
		}
		// 현재 작업시간이 최솟값과 같으면서 현재 높이가 더 높다면 갱신
		if (currentTime == t)
		{
			if (height < h)
				height = h;
		}
	}

	cout << t << " " << height;
}

void Input()
{
	cin >> col >> row >> ownBlocks;
	totalBlockAmount += ownBlocks;

	for (int y = 0; y < col; y++)
	{
		for (int x = 0; x < row; x++)
		{
			cin >> map[y][x];
			totalBlockAmount += map[y][x];
		}
	}
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	Input();
	Solution();

	return 0;
}