본문 바로가기

Problem Solving/Algorithm Training

[Baekjoon] 18111 - 마인크래프트 (C++)

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

 

18111번: 마인크래프트

팀 레드시프트는 대회 준비를 하다가 지루해져서 샌드박스 게임인 ‘마인크래프트’를 켰다. 마인크래프트는 1 × 1 × 1(세로, 가로, 높이) 크기의 블록들로 이루어진 3차원 세계에서 자유롭게 땅을 파거나 집을 지을 수 있는 게임이다. 목재를 충분히 모은 lvalue는 집을 짓기로 하였다. 하지만 고르지 않은 땅에는 집을 지을 수 없기 때문에 땅의 높이를 모두 동일하게 만드는 ‘땅 고르기’ 작업을 해야 한다. lvalue는 세로 N, 가로 M 크기의 집터를

www.acmicpc.net

블록을 설치하거나 제거해서 땅을 평평하게 만들어 줘야 합니다. 블록을 설치할 때는 1초, 제거할 때는 2초가 걸립니다. 땅의 크기와 높이, 초기 블록의 개수가 주어졌을 때, 땅을 평평하게 만들 수 있는 최소 시간과 그때의 높이를 구해야 하는 문제입니다.

 

어떻게 풀까 고민하다가 생각보다 입력값의 범위가 그렇게 크지 않은 것 같아서 그냥 모든 경우의 수를 고려해서 풀어도 괜찮을 것 같다는 생각이 들었습니다.

 

특정한 높이에서 땅을 평평하게 만들 때 걸리는 시간을 구하는 것은 생각보다 간단합니다. 특정한 높이를 기준으로 더 높게 있는 땅은 제거하고, 더 낮게 있는 땅에 블록을 설치해 주기만 하면 됩니다. 이제 이걸 가능한 경우의 높이에서 모두 계산해보고 나온 시간을 비교해 최솟값을 구해주면 되겠죠?

 

풀이 방법은 이렇습니다. 먼저 입력으로 주어진 땅에서 최소 높이와 최대 높이를 찾고, 최소 높이에서 최대 높이까지 땅을 평평하게 만드는 데 걸리는 시간을 전부 계산했습니다. 그리고 그중에서 최솟값을 찾아 주었죠. 시간 계산의 경우 현재 높이보다 더 높은 블록의 개수와 더 낮은 블록의 개수를 구한 뒤에 상황에 맞게 계산만 하면 됩니다.

 

처음에는 입력으로 주어진 땅 자체가 이미 평평한 상황인 경우를 고려하지 못해서 오답을 받았습니다. 항상 문제를 잘 읽어보고 조건을 명확히 따져보는 습관을 길러야 할 것 같습니다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>

using namespace std;

vector<vector<int>> world;
int n, m, b;

int makeFlat(int height)
{
	int higherCount = 0;
	int lowerCount = 0;

	// 현재 높이보다 높거나 낮은 블록의 개수를 구함
	for (int y = 0; y < n; y++) {
		for (int x = 0; x < m; x++) {
			if (world[y][x] > height) higherCount += world[y][x] - height;
			else if (world[y][x] < height) lowerCount += height - world[y][x];
		}
	}

	// 블록 변화가 없을 경우
	if (higherCount == 0 && lowerCount == 0) {
		return 0;
	}

	// 블록이 부족할 경우 불가능
	if (lowerCount > higherCount + b) {
		return -1;
	}

	// 걸리는 시간 계산
	return higherCount * 2 + lowerCount;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n >> m >> b;

	int maxHeight = 0, minHeight = INT_MAX;
	int answerTime = INT_MAX, answerHeight = 0;
	world.resize(n, vector<int>(m));

	// 땅의 높이 정보 입력
	for (int y = 0; y < n; y++) {
		for (int x = 0; x < m; x++) {
			cin >> world[y][x];

			// 최대 높이와 최소 높이를 기록
			maxHeight = max(maxHeight, world[y][x]);
			minHeight = min(minHeight, world[y][x]);
		}
	}

	// 가능한 모든 높이에 대해 시간을 계산하고 최솟값을 기록
	for (int i = minHeight; i <= maxHeight; i++) {
		int elapsedTime = makeFlat(i);

		if (elapsedTime >= 0 && answerTime >= elapsedTime) {
			answerTime = elapsedTime;
			answerHeight = i;
		}
	}

	cout << answerTime << " " << answerHeight << "\n";
	return 0;
}