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

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

18111번: 마인크래프트

높이를 구하는 문제이기에 처음에는 이분탐색으로 풀수 있을거라고 생각했다.

하지만 여러케이스를 상성하고 고려해 보았을때 특정 높이로 땅을 고를수 있다고 했을때 어떠한 기준으로 범위를 좁혀나갈지를 정하는 것이 불가능했다.

지금까지 나온 시간중 최소시간이라고 하더라도 더 높은 곳에 최소시간을 갖는 높이가 존재할 수도 있고 더 낮은 곳에 최소시간을 갖는 높이가 존재할 수 있기 때문이다.

 

고민끝에 brute force방식으로 구현하였다.

0~256의 모든 높이에 대해 땅 고르는 시간을 구하고 그 중에서 최소값과 그 높이를 찾아 출력한다.

고려해야할 점이 한가지 있는데, 이는 해당높으로 땅을 고를 수 있느냐 하는 것이다. 인벤토리안에 주어진 B와 땅을 고르기 위해 파낸 땅의 개수가 target 높이를 맞추기 위해 놓은 땅의 개수보다 작으면 안된다.

 

#include <iostream>

using namespace std;

int main(){
    int n, m, b;
    int input[500][500]={0,};
    int sum = 0, min=987654321, h_index=0;
    int in_ground = 0, out_ground = 0;

    //input
    scanf("%d %d %d", &n, &m, &b);
    for (int i = 0; i < n; i++){
        for (int j = 0; j < m; j++){
            scanf("%d", &input[i][j]);
        }
    }

    //solved
    for (int h = 0; h <= 256; h++){
        sum = 0, in_ground = 0, out_ground = 0;
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
            {
                if(h - input[i][j] > 0){
                    sum += (h - input[i][j]); // 땅을 심어야하는 경우
                    in_ground += h - input[i][j];
                }
                if (h - input[i][j] < 0)
                {
                    sum += (input[i][j] - h)*2; // 땅을 파야하는 경우
                    out_ground += input[i][j] - h;
                }
            }
        }
        if(in_ground<=out_ground+b && min >= sum){
            min = sum;
            h_index = h;
        }
    }
    printf("%d %d", min, h_index);
    return 0;
}