[BOJ] 18111 마인크래프트

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

18111번: 마인크래프트

---------------------------------------------------핵심 알고리즘--------------------------------------------

 

brute-force

 

---------------------------------------------------풀이----------------------------------------------------

 

맵의 각 위치에서 블록의 개수의 최소와 최대를 구하고,

최소부터 최대까지 맵을 고르게 만드는 작업을 수행한다.

inventory는 B로 시작해서 블록을 제거한 만큼 +되고, 블록을 놓은 만큼 -된다.

최종적으로 inventory가 0이상일 경우, 땅 고르기 작업이 수행될 수 있음을 의미하고,

그 경우 중에서 시간이 최소인 경우, 시간이 같다면 높이가 최대인 경우를 구한다.

#define FASTIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#include <stack>

using namespace std;

// (i,j)의 블록 하나 제거 -> 2초
// (i,j)에 블록 하나 놓기 -> 1초
// 땅 고르기 작업에 걸리는 최소 시간과 그 경우 땅의 높이=?
// 인벤토리에는 B개의 블록이 들어있음. 땅의 높이는 256 초과할 수 없음.
int main(void){
    FASTIO;
    int N, M, B;
    cin >> N >> M >> B;
    int map[501][501] = {0, };
    int min = 512, max = -1;
    for(int i = 0; i < N; i++){
        for(int j = 0; j < M; j++){
            cin >> map[i][j];
            if(map[i][j] < min){
                min = map[i][j];
            }
            if(map[i][j] > max){
                max = map[i][j];
            }
        }
    }
    int ans_time = 99999999;
    int ans_height = 0;
    // min부터 max까지 땅의 높이를 만들면서 최소 시간일 경우 구하기
    for(int i = min; i <= max; i++){
        int cur_time = 0;
        int inventory = B;
        for(int j = 0; j < N; j++){
            for(int k = 0; k < M; k++){
                if(map[j][k] > i){
                    cur_time += (map[j][k]-i)*2;
                    inventory += map[j][k] - i;
                }
                else{
                    cur_time += i-map[j][k];
                    inventory -= i - map[j][k];
                }
            }
        }
        if(inventory >= 0 && cur_time <= ans_time){
            ans_time = cur_time;
            ans_height = i;
        }
    }
    cout << ans_time << " " << ans_height << "\n";
    return 0;
}

 

---------------------------------------------------후기----------------------------------------------------

 

ans_time을 9999999로 설정해서 틀렸었다.

앞으로는 귀찮아도 그냥 limits.h의 INT_MAX로 적어주자!