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

Approach

수능 수학 문제처럼 높이를 고정시켜둔 상태에서의 cost를 구하는 것은 크게 어렵지 않다.

추가적으로 나올 수 있는 높이는 0 ~ 256까지이므로, 연산이 최대로 많아봐야 500 * 500 * 256이고 이는 1억 미만이다.

 

따라서 Brute force적으로 접근해도 시간 안에 통과할 수 있다.

Code

#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0)

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
int move_x[4] = {-1, 1, 0, 0};
int move_y[4] = {0, 0, -1, 1};


int main() {
    int n, m, b;
    cin >> n >> m >> b;

    int r[500][500];

    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            cin >> r[i][j];
        }
    }
    int min_cost = INT_MAX;
    int min_height;

    for(int i = 256; i >= 0; --i){
        int height = i;
        int cur_cost = 0;
        int cur_block = b;
        for(int j = 0; j < n; ++j){
            for(int k = 0; k < m; ++k){
                int diff = r[j][k] - height;
                cur_cost += (diff > 0) ? diff * 2 : -diff;
                cur_block += diff;
            }
        }
        if(cur_block < 0) cur_cost = INT_MAX;
        if(cur_cost < min_cost){
            min_cost = cur_cost;
            min_height = height;
        }
    }
    cout << min_cost << " " << min_height << "\n";
    return 0;
}