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

안녕하세요. 오늘 풀어볼 문제는 백준 마인크래프트 입니다.

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

 

마인크래프트는 구현 문제에요.

줄글로는 직관적이지만 막상 소스 코드로 옮기려면 여러가지로 고려해야 할 것들이 있습니다.

 

마인크래프트라는 게임을 모른다면 줄글을 이해하는데도 시간이 걸릴 수 있겠네요.

 

DP로 해결해야 하나? 라는 생각이 들 수도 있지만 각 원소가 서로 연관이 없고 높이끼리도 독립적이기 때문에 그럴 필요는 없습니다.

 

모든 높이 h애 대해 h를 만들기 위해 설치해야 할 블럭의 개수, 제거해야할 블럭의 개수를 구하면 h를 만들기 위한 시간도 알 수 있습니다.

 

h를 만들기 위해 설치해야 할 블럭의 개수는 모든 원소에 대해 아래 라인을 수행하면 얻을 수 있습니다.

if (map[x][y] > h) remove += map[x][y] - h

 

h를 만들기 위해 제거해야 할 블럭의 개수를 위한 라인은

if (map[x][y] < h) place += h - map[x][y]

 

인벤토리에 설치할만큼의 블럭이 있어야 하기 때문에 해당 조건도 검사해야겠네요.

 

아래는 코드 전문

#include <iostream>
using namespace std;

int N, M, B;
int highest = 0, least = 999999999, height;
int map[501][501];

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

	cin >> N >> M >> B;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> map[i][j];
			highest = max(map[i][j], highest);
		}
	}

	for (int h = 0; h <= highest; h++) {
		int place = 0, remove = 0;
		for (int x = 0; x < N; x++) {
			for (int y = 0; y < M; y++) {
				if (map[x][y] > h) remove += map[x][y] - h;
				else if (map[x][y] < h) place += h - map[x][y];
			}
		}

		if (place > B + remove) continue;

		int t = remove * 2 + place;
		if (least >= t) {
			least = t;
			height = h;
		}
	}

	cout << least << ' ' << height;
}