❓문제 설명

문제 : 백준 18111 마인크래프트
난이도 : 실버 2

문제 요약

• 세로, 가로, 높이가 각각 1인 블록들이 존재합니다.
• 땅고르기 작업은 모든 땅의 높이가 같아지게 하는 작업을 의미합니다.
• 세로 N, 가로 M 크기의 집터를 골랐을 때 모든 땅을 2가지 작업을 통해 고르게 해야합니다.
  1. 좌표 (i, j)의 가장 위에 있는 블록을 제거하여 인벤토리에 넣는다.
  2. 인벤토리에서 블록 하나를 꺼내어 좌표 (i, j)의 가장 위에 있는 블록 위에 놓는다.
• 1번 작업은 2초, 2번 작업은 1초가 걸립니다. 블록의 최대 높이는 256을 넘을 수 없고 음수 또한 될 수 없습니다.
• 이때 작업에 걸리는 최소 시간과 그 경우 땅의 높이를 출력하면되는 문제 입니다.

인벤토리에 블록의 수가 1개 이상이라면 63이 있는 위치에 블록을 하나 둬서 모든 땅의 높이를 64로 맞추면 1초만에 작업을 마무리 할 수 있습니다.

🎯문제 해결 방법

이 문제는 최소 시간에 땅을 고르게 할 것 같은 높이를 정하고 완전탐색을 통해 최소 시간을 구하는 문제 입니다.

첫 번째 시도

	set<int> s; // 땅고르기를 할 기준이 되는 높이들
    ...
	for(int i=0; i<n; i++){
		for(int j=0; j<m; j++){
			cin >> a[i][j];
			s.insert(a[i][j]); // 주어진 땅의 높이들로만 기준을 잡기 위해 set에 저장
		}
	}

	for(auto e: s){
		int x = 0; //build
		int y = 0; //remove
		for(int i=0; i<n; i++){
			for(int j=0; j<m; j++){
				if(a[i][j] > e) {
					y += a[i][j] - e; // 기준 땅이 더 낮을 땐 지워야 할 땅의 수를 높이 차 만큼 늘려줍니다.
				} else if(a[i][j] < e){
					x += e - a[i][j]; // 기준 땅이 더 높을 땐 쌓아야 하는 블록의 수를 높이 차 만큼 늘려줍니다.
				}
			}
		}
		if(y + b >= x) { // 지워서 얻은 블록의 수와 기존의 블록의 수를 합친게 쌓아햐 하는 블록의 수보다 많을 경우에만 가능합니다. 
			int time = y * 2 + x; // 지우는 과정에서 2초, 쌓는 과정에서 1초로 시간을 계산해줍니다.
			if(mn >= time){
				mn = time;
				h = e;
			}
		}
	}

틀린이유

• 높이는 0부터 256까지만 가능하도록 정해주었습니다.
• 제가 쓴 코드는 set을 통해서 맵에 주어진 높이들로만 확인을 했고 기준이 될 수 있는 높이는 맵에 주어진 높이가 아닌 경우가 있기 때문에 위 코드는 잘못된 완전탐색 코드입니다.

두 번째 시도

	for(int e = 0; e <= 256; e++){
		int x = 0; //build
		int y = 0; //remove
		for(int i=0; i<n; i++){
			for(int j=0; j<m; j++){
				if(a[i][j] > e) {
					y += a[i][j] - e;
				} else if(a[i][j] < e){
					x += e - a[i][j];
				}
			}
		}
		if(y + b >= x) {
			int time = y * 2 + x;
			if(mn >= time){
				mn = time;
				h = e;
			}
		}
	}

기존 코드는 그대로 두고 기준이 되는 높이만 0부터 256 까지 확인하는 과정으로 바꾸어줬습니다.

💻전체 코드

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int n,m,b;
int a[504][504];
int mn = 987654321;
int h;
int main(void){
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> n >> m >> b;
	for(int i=0; i<n; i++){
		for(int j=0; j<m; j++){
			cin >> a[i][j];
			s.insert(a[i][j]);
		}
	}
	
	for(int e = 0; e <= 256; e++){
		int x = 0; //build
		int y = 0; //remove
		for(int i=0; i<n; i++){
			for(int j=0; j<m; j++){
				if(a[i][j] > e) {
					y += a[i][j] - e;
				} else if(a[i][j] < e){
					x += e - a[i][j];
				}
			}
		}
		if(y + b >= x) {
			int time = y * 2 + x;
			if(mn >= time){
				mn = time;
				h = e;
			}
		}
	}
	cout << mn << " " << h;
	return 0;
}