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

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

18111번: 마인크래프트

---

풀이

1. 모든 땅의 높이만 같으면 되므로 N*M 크기의 땅을 선형변환 -> a[N*M]
2. 모든 땅의 높이 중 최고 높이과 최저 높이 사이의 값이 땅을 고르는 높이가 될 수 있음
3. 땅을 고르게 될 높이별로 땅을 고르는 시간 측정 -> 최솟 값 저장
4. 이때 고르는 작업에 의한 인벤토리의 블록 개수 측정
   -> 음수라면 불가능한 작업이므로 시간 측정 배제
   -> 이때 작은 수에서 큰 수로 땅의 높이를 증가하면서 검사한다면, 작업 종료 후 인벤토리의 값이 음수가 되었을 때, 더 높은 높이의 땅들도 마찬가지로 블록이 부족하므로 작업이 불가능함 -> 반복문 종료(시간 단축)

---

답

#include <iostream>
#include <algorithm>
#include <climits>
using namespace std;

int main()
{
    int N, M, B;
    cin >> N >> M >> B;
    N = N * M;
    int a[N];
    for (int i = 0; i < N; i++)
    {
        cin >> a[i];
    }
    sort(a, a + N);
    int time = INT_MAX, high;
    for (int h = a[0]; h <= a[N - 1]; h++)
    {
        int t = 0;
        int block = B;
        for (int i = 0; i < N; i++)
        {
            if (h > a[i])
            {
                block += a[i] - h;
                t += h - a[i];
            }
            else if (h < a[i])
            {
                block += a[i] - h;
                t += 2 * (a[i] - h);
            }
        }
        if (block < 0)
            break;
        if (t <= time)
        {
            time = t;
            high = h;
        }
    }
    cout << time << " " << high;
}