[BOJ/C++] 18111번 - 마인크래프트

1. 문제 링크

BOJ 18111번 - 마인크래프트

2. 걸린 시간

30분

3. 문제

4. 문제 풀이

• 땅 블럭 하나를 집어서 인벤토리에 넣음 → 2초
• 인벤토리에 있는 땅 블럭을 땅에 올림 → 1초

가장 최소 시간이 걸리는 땅 고르기(모든 땅의 높이를 동일하게)를 수행해라!

전체 코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int N, M, B;
int lowest_height = 256, highest_height = 0;

int main() {
	cin >> N >> M >> B;

	vector<vector<int>> ground(N, vector<int>(M, 0));

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

			if (input < lowest_height) lowest_height = input;
			if (input > highest_height)	highest_height = input;
		}
	}

	int min_sec = 1e9;
	int ans_height = 0;
	for (int height = lowest_height; height <= highest_height; height++) {
		int copy_B = B, sec = 0;
		vector<pair<int, int>> lower_grounds;

		for (int x = 0; x < N; x++) {
			for (int y = 0; y < M; y++) {
				if (ground[x][y] == height) continue;
				else if (ground[x][y] > height) {
					copy_B += (ground[x][y] - height);
					sec += (ground[x][y] - height) * 2;
				}
				else {
					lower_grounds.push_back(make_pair(x, y));
				}
			}
		}

		bool success = true;  // 땅 고르기 성공 여부 
		for (auto& pos : lower_grounds) {
			int x = pos.first, y = pos.second;
			copy_B -= (height - ground[x][y]);
			if (copy_B < 0) success = false;  // 남는 블록이 없다면 
			sec += (height - ground[x][y]);
		}
		
		if (success && sec <= min_sec) {
			min_sec = sec;
			ans_height = height;
		}
	}
	cout << min_sec << " " << ans_height << '\n';
}

나는 브루트포스로 문제를 풀었다.

그래서 땅의 높이를 입력받을 떄 바로 lowest_height, highest_height를 갱신했다.
그리고 문제에서는 같은 시간이 걸릴 때, 가장 높은 높이로 출력하라고 했으므로 lowest_height부터 순회해주면 손쉽게 이를 만족할 수 있다.

인벤토리에 있는 블록의 개수가 음수가 되면 안된다. 그래서 lower_grounds에 height보다 낮은 땅의 높이가 나올 때 저장해두고 나중에 처리했다.

즉, height보다 높거나 같은 땅의 높이만 우선 처리해서 인벤토리에 블록을 모두 저장해주고 나중에 인벤토리에 저장된 블록들을 꺼내 땅 위에 쌓는다는 것이다.

여러 경우를 확인해주어야 하므로 B의 값을 변경하면 안된다. 그래서 copy_B로 B의 복사값으로 순회를 해준다.

height보다 낮은 땅들을 처리해주면서 인벤토리에 저장된 땅의 개수인 copy_B가 음수가 되면 이는 제대로 땅 고르기를 못한다는 뜻이다.
그러므로 success를 false 처리해줌으로써 땅 고르기에 든 최소 시간인 min_sec 갱신을 뛰어넘는다.

5. 배운 점

문제를 풀 때는 센스가 중요한 것 같다.

lowest_height부터 처리해줌으로써 굳이 같은 시간이 걸리는 경우가 여러 개 발생할 때, 따로 처리해주지 않아도 된다.

솔직히 나도 구현하고 나서 내 센스에 조금 놀람(^///^)

1년 반 전에 도전했다가 포기했었는데, 이번에 푸니까 감회가 새롭다.
그래도 1년 반 헛살지 않은 것 같다!