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

문제: www.acmicpc.net/problem/18111

18111번: 마인크래프트

 

문제풀이

 

모든 경우의 수를 비교하는 브루트 포스 문제이다.

 

먼저 땅의 높이 최솟값과 최댓값을 구한 뒤 땅을 최솟값으로 평탄화할 시의 시간부터 땅을 최댓값으로 평탄화할시의 시간까지 모두 비교하여 결과를 구했다.

 

만일 인벤토리가 0 미만이라면 물리적으로 평탄화가 불가능하기 때문에 continue() 함수로 패스한다.

 

 

코드

#include <iostream>
#include <climits>

using namespace std;

int main(){
    ios::sync_with_stdio(false); cin.tie(NULL);

    int N,M,B;
    cin>>N>>M>>B;

    int max=0;
    int min=256; //땅의 높이는 0 이상 256 이하
    int arr[N][M];
    for(int i=0; i<N; i++){
        for(int j=0; j<M; j++){
            cin>>arr[i][j];

            if(arr[i][j] > max) //최대 땅의 높이
                max = arr[i][j];

            if(arr[i][j] < min) //최소 땅의 높이
                min = arr[i][j];
        }
    }

    /*
    최소 땅의 높이에서의 작업시간에서 최대 땅의 높이에서의 작업시간까지 모두 비교해본다.
    */
    int resultheight;
    int resultTime = INT_MAX;
    for(int height=min; height<=max; height++){
        int time = 0;
        int inventory = B;
        for(int i=0; i<N; i++){
            for(int j=0; j<M; j++){
                if(arr[i][j] == height){
                    continue;
                }
                else if(arr[i][j] > height){
                    inventory += arr[i][j] - height;
                    time += (arr[i][j] - height)*2;
                }
                else{
                    inventory -= height - arr[i][j];
                    time += height - arr[i][j];
                }
            }
        }

        if(inventory < 0) //인벤토리가 0 미만이라면 continue
            continue;

        if(resultTime >= time){ //시간이 같더라도 최대 땅의 높이를 결과로 출력하기위해 '>=' 조건
            resultTime = time;
            resultheight = height;
        }
    }
    
    cout<<resultTime<<" "<<resultheight;

    return 0;
}

 

결과

처음 문제를 풀었을 때 루프 마지막 부분의 "resultTime >= time" 조건문을 "resultTime > time"로 주었기 때문에 최소 시간은 문제없었으나 문제의 조건인 최대 땅의 높이를 구하지 못해 헤매었다.