(C++) - 백준(BOJ) 18111번 : 마인크래프트 답

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

18111번: 마인크래프트

높이를 천천히 낮춰가며 최소시간과 가장 높은 높이를 구하는 구현, brute force 문제였습니다.

 

풀이방법 : 

 1. 높이 확인 : 최소 높이는 0 최대 높이는 256까지 loop

 2. 채워야할 블록개수 지워야할 블록개수 계산 :

    if(맵의 한 타일에서 높이 - 정한높이가 양수) => 지워야할 블록 개수

    else => 채워야할 블록 개수

 3. 높이와 걸린 시간 갱신

    if(지울 블록의 개수 + 처음에 가지고 있던 인벤토리 블록의 개수 >= 채울 블록 개수)

    => 소요시간 : 지울 블록 개수 * 2 + 채울 블록 개수

         if(소요시간이 작다면) 시간 갱신

 4. 답 출력

 

Code :

#include <iostream>
using namespace std;
int main() {
    int n, m, b;
    int map[500][500];
    int leastTime = 0x7f7f7f7f;
    int mostHeight;
    cin >> n >> m >> b;
	for (int i = 0; i < n; i++) 
		for (int j = 0; j < m; j++) 
			cin >> map[i][j];

	for (int h = 0; h <= 256; h++) {
		int build = 0;
		int remove = 0;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				int height = map[i][j] - h;
				if (height > 0) remove += height;
				else if (height < 0) build -= height;
			}
		}
		//지울것 + 인벤토리 블록 >= 채울것
		if (remove + b >= build) {
			int time = remove * 2 + build;
			if (leastTime >= time) {
				leastTime = time;
				mostHeight = h;
			}
		}
	}
    cout << leastTime << ' ' << mostHeight <<'\n';
}