[백준] 18111번

문제에서 조건을 잘봐야할 듯하다.

0~255라는 부분이 가장 큰 핵심 중 하나고, 블럭 수가 두번째 key다.

블럭 수가 key인 이유는 block이 -에서 +로 변하는 시점에서 나온 값이 최소 값이 나타나는 시점으로 볼 수 있기 때문이다.

그 전까지는 계속 base height를 줄여 나가면서 해결해야 한다.

#include <algorithm>
#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <climits>

int main() {
    int n, m, b;
    std::cin >> n >> m >> b;
    std::vector<int>height(n*m);
    std::set<int> base;
    std::map<int, bool> visited;
    int minH = INT_MAX;
    int maxH = 0;
    for (int i = 0; i < n*m; i++) {
        std::cin >> height[i];
        base.insert(height[i]);
        if (height[i] < minH) {
            minH = height[i];
        }
        if (height[i] > maxH) {
            maxH = height[i];
        }
    }
    int time = INT_MAX, h = 0;
    for (int _h : base) {
        for (int i = _h; i >= minH; i--) {
            int _time = 0; int _b = b;
            if (visited[i]) {
                continue;
            }
            for (int j = 0; j < n*m; j++) {
                if (height[j] > i) {
                    _time += 2*(height[j] - i);
                    _b += (height[j] - i);
                } else if (height[j] < i) {
                    _time += (i - height[j]);
                    _b -= (i - height[j]);
                }
            }
            visited[i] = true;
            if (_time < time && _b >= 0) {
                time = _time;
                h = i;
            } else if (_time == time && _b >= 0 && h < i) {
                h = i;
            }
        }
    }

    std::cout << time << " " << h << std::endl;
    return 0;
}