백준 18111번 : 마인크래프트 C++ 코드

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

18111번: 마인크래프트

 

높이를 0부터 256까지 모두 확인해주어야 문제를 해결할 수 있다.

 

초기 배열의 값들을 기준으로 높이를 설정해 최소시간을 구했는데

 

초기 배열에 존재하지 않는 값이 최소시간의 땅의 높이가 될 수 있다.

 

#include <bits/stdc++.h>
using namespace std;

int n, m, b, arr[501][501];
int height=-1, cnt = INT_MAX;

void func(int x) {
    int test_b = b;
    int test_cnt = 0;
    int test[501][501];

    copy(&arr[0][0], &arr[0][0] + 501 * 501, &test[0][0]);

    //파내기 먼저 해줘서 b를 확보한다
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (test[i][j] > x) {
                test_cnt += 2 * (test[i][j] - x);
                test_b += (test[i][j] - x);
                if (test_cnt > cnt) return;
            }
        }
    }

    //쌓기
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (test[i][j] < x) {
                test_b -= (x - test[i][j]);
                if (test_b < 0) return;
				test_cnt += (x - test[i][j]);

				if (test_cnt > cnt) return;
            }
        }
    }


    if (cnt > test_cnt) {
        cnt = test_cnt;
        height = x;
    }
    else if (cnt == test_cnt) {
        if (x > height) height = x;
    }

}


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

    cin >> n >> m >> b;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> arr[i][j];
        }
    }

    for (int i = 0; i <= 256; i++) {
        func(i);
    }

    cout << cnt << ' ' << height << '\n';

    return 0;
}

백준 18111번