[백준] 18111 마인크래프트

백준 18111 마인크래프트

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

18111번: 마인크래프트

 

[문제]

집을 짓는데 집터를 다지는 문제이다.

집터의 땅의 높이를 일정하게 만들어 평평하게 만들어야 한다!

두 종류의 작업을 할 수 있다.

 

1. 좌표 (i, j)의 가장 위에 있는 블록을 제거하여 인벤토리에 넣는다.
2. 인벤토리에서 블록 하나를 꺼내어 좌표 (i, j)의 가장 위에 있는 블록 위에 놓는다.

 

1번 작업은 2초가 걸리며, 2번 작업은 1초가 걸린다.

최대한 빨리 땅 고르기 작업을 마쳐야 한다.

 

[입력]

첫째 줄에 N, M, B가 주어진다. (1 ≤ M, N ≤ 500, 0 ≤ B ≤ 6.4 × 107)

둘째 줄부터 N개의 줄에 각각 M개의 정수로 땅의 높이가 주어진다.  (i + 2)번째 줄의 (j + 1)번째 수는 좌표 (i, j)에서의 땅의 높이를 나타낸다.

땅의 높이는 256보다 작거나 같은 자연수 또는 0이다.

 

[출력]

땅을 고르는 데 걸리는 시간과 땅의 높이를 차례로 출력한다.

---

[해결]

높이가 최소 0 이상이므로 0부터 최대 높이까지 탐색을 하면서, 최소 시간으로 땅을 평평하게 하는 높이를 찾아야 한다.

 

1. 최대 높이를 찾는 함수를 이용해서 탐색할 높이의 범위를 정한다.

2. 해당 높이로 땅을 평평하게 만들 때 걸리는 시간을 구한다.

3. 만약, block의 값이 음수라면, 해당 높이로 땅을 평평하게 할 수 없다는 것이므로 -1을 반환한다.

4. 걸리는 시간 중 최소 값을 출력한다.

 

 

#include <iostream>

using namespace std;

int		n, m, b;
int		map[501][501] = {0, };

//find max height
int		find_max(){
	int		max = 0;

	for (int i = 0; i < n; i++){
		for (int j = 0; j < m; j++){
			if (map[i][j] > max)
				max = map[i][j];
		}
	}
	return max;
}

//check the time
int		check(int height){
	int	time = 0;
	int	block = b;

	for (int i = 0; i < n; i++){
		for (int j = 0; j < m; j++){
			if (map[i][j] > height){
				time += (map[i][j] - height) * 2;
				block += map[i][j] - height;
			}else if (map[i][j] < height){
				time += height - map[i][j];
				block -= height - map[i][j];
			}
		}
	}
	if (block < 0)
		return -1;
	return time;
}

int		main(){
	int		max, height, time, tmp;
	//input
	cin >> n >> m >> b;
	for (int i = 0; i < n; i++){
		for (int j = 0; j < m; j++)
			cin >> map[i][j];
	}
	max = find_max() + 1;
	time = 1000000000;
	height = 0;
	while (--max >= 0){
		tmp = check(max);
		if (tmp != -1 && tmp < time){
			time = tmp;
			height = max;
		}
	}
	cout << time << " " << height << endl;
	return 0;
}