no.18111 마인크래프트

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

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

    int N, M, B;
    cin >> N >> M >> B;

    vector<vector<int>> grid(N, vector<int>(M, 0));
    int minTime = INT32_MAX, targetHeight = 0;

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> grid[i][j];
        }
    }

    for (int h = 0; h <= 256; h++) {
        int removeBlocks = 0, addBlocks = 0;

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (grid[i][j] > h) {
                    removeBlocks += grid[i][j] - h; 
                }
                else {
                    addBlocks += h - grid[i][j];   
                }
            }
        }

        if (removeBlocks + B >= addBlocks) {
            int time = removeBlocks * 2 + addBlocks; 

            if (time < minTime || (time == minTime && h > targetHeight)) {
                minTime = time;
                targetHeight = h;
            }
        }
    }

    cout << minTime << " " << targetHeight << "\n";
    return 0;
}

 

맨처음 문제를 본 생각은 

1.256개의 높이중에서 가장 많이 나온 높이의 블럭 양을 측정해서

2.그 높이를 기준으로 블럭 작업을 해주면 되겠구나! 

라는 생각이었다. 이는 참 안일한 생각이었는데 이러한 방식으로 할경우,

결과값이 가지고 있는 블럭과 동일하거나 블럭보다 작은 경우의 알고리즘과

결과값이 가지고 있는 블럭보다 큰 경우의 알고리즘을 따로 작성해주어야 했던것이다.

 

문제풀이

문제는 브루트 포스 방식으로 1~256블럭까지 모든 높이의 환경을 가정한후, 

그에 필요한 블럭 개수와 시간을 측정해 주고 

1. 제거한 블럭+ 가지고 있던 블럭을 이용해서 모든 블럭 추가가 가능한지 확인

2.만약 가능하다면 h의 높이에서 평탄화 시키는 시간이 현재 가장 최소로 필요한 시간보다 적게 필요하거나

   시간이 동일하다면 h의 높이가 더 높을때만 

답인 minTime과 목표 높이를 갱신시켜주면 된다.

 if (removeBlocks + B >= addBlocks) {
     int time = removeBlocks * 2 + addBlocks; 

     if (time < minTime || (time == minTime && h > targetHeight)) {
         minTime = time;
         targetHeight = h;
     }
 }

바로 이부분이 될 것이다.

 

언뜻 보면 해당된 범위 내에서의 값 탐색 같지만, 모든 경우의 수를 탐색해야된다는 것이 핵심이었다.