[Silver 2] 18111 마인크래프트

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

 

N x M 크기의 땅 정보를 입력 받을 때 최소 높이의 블록과 최대 높이 블록을 구한다.

이후 최소 높이에서 최대 높이까지 땅 높이를 조사한다.

현재 높이에서 arr배열 속 땅 정보가 크면 땅을 판다.

또한 현재 높이에서 arr배열 속 땅 정보가 작으면 땅을 채운다.

 

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

int N, M, B;
int arr[501][501];
int minBlock = 257, maxBlock = 0;
int answer = 987654321, height = -1;

void dfs(int h, int b){
    int t = 0;

    for(int i = 0;i<N;i++){
        for(int j = 0;j<M;j++){
            if(arr[i][j] > h){
                b += arr[i][j] - h;
                t += 2 * (arr[i][j] - h);
            }
        }
    }
    for(int i = 0;i<N;i++){
        for(int j = 0;j<M;j++){
            if(arr[i][j] < h){
                b -= h - arr[i][j];
                t += 1 * (h - arr[i][j]);
            }
        }
    }
    if(b >= 0){
        answer = min(answer, t);
        if(answer == t)
            height = max(height, h);
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
	cin>>N>>M>>B;

    for(int i = 0;i<N;i++){
        for(int j = 0;j<M;j++){
            cin>>arr[i][j];
            minBlock = min(arr[i][j], minBlock);
            maxBlock = max(arr[i][j], maxBlock);
        }
    }
    for(int i = minBlock; i<=maxBlock;i++)
        dfs(i,B);

    cout<<answer<<' '<<height<<'\n';
}