[백준/BOJ] 18111번 마인크래프트 (C++)

www.acmicpc.net/problem/18111

18111번: 마인크래프트

브루트 포스(완전 탐색) 유형의 문제였습니다.

블록의 높이가 최대 256에 2차원 배열이 최대 500x500이므로 시간복잡도가 256 x 500 x 500 = 64,000,000로 충분히 완전 탐색으로 해결할 수 있습니다. 인벤토리에 블록을 꺼내어 놓기, 블록을 제거하여 인벤토리에 넣기, 아무것도 안하기 세가지 경우를 고려해야하는데, 첫번째 경우에서 인벤토리가 0보다 작은 경우까지 고려하다보니 너무 예외처리가 복잡해졌습니다. 따라서 블록의 높이만 비교하고, 나중에 인벤토리가 0보다 작은지 확인하는 걸로 고쳤습니다. 이렇게 하면 예외처리가 매우 간단해지고, 인벤토리가 0보다 큰 경우만 시간의 최소값과 높이를 갱신하면 됩니다.

 

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

int map[501][501];

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int n, m, b, time = 2147000000, height;
    cin>>n>>m>>b;
    
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            cin>>map[i][j];
        }
    }
    
    // 블록의 높이 0~256까지 완전탐색  
    for(int k = 0; k <= 256; k++) {
        int sum = 0, tmp = b;
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                // 인벤토리에서 블록을 꺼내어 놓는다 : 1초
                if(map[i][j] < k) {
                    sum += k - map[i][j];
                    tmp -= k - map[i][j];
                // 블록을 제거하여 인벤토리에 넣는다 : 2초	
                } else if(map[i][j] > k) {
                    sum += (map[i][j] - k) * 2;
                    tmp += map[i][j] - k; 
                // 연산을 안한다. : continue
                } else {
                    continue;
                }
            }
        }
        
        // 현재 k의 탐색이 마치고난 후 인벤토리가 0보다 작다면 불가능한 경우
        if(tmp >= 0) {
            if(sum <= time) {
                time = sum;
                height = k;
            }
        }
    }

    cout<<time<<" "<<height;
}