마인크래프트 (feat. 백준, 18111번)

마인크래프트
https://www.acmicpc.net/problem/18111

18111번: 마인크래프트

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
struct cmp{
    bool operator()(const pair<int, int>& v1, const pair<int, int>& v2) const{
        if(v1.first == v2.first)
            return v1.second < v2.second;
        return v1.first > v2.first;
    }
};
int main(){
    ios::sync_with_stdio(false), cin.tie(NULL);
    register int N, M, B, arr[501][501];
    priority_queue<pair<int, int>, vector<pair<int, int>>, cmp> ans;
    cin >> N >> M >> B;
    for(register int n = 0, m; n < N; ++n)
        for(m = 0; m < M; ++m)
            cin >> arr[n][m];
    for(register int h = 0, t1, t2, n, m, hh; h <= 256; ++h){
        t1 = t2 = 0;        // 제거할 블록 t1, 추가할 블록 t2
        for(n = 0; n < N; ++n)
            for(m = 0; m < M; ++m){
                hh = arr[n][m] - h;
                if(hh > 0)          t1 += hh;
                else if(hh < 0)     t2 += -hh;
            }
        if(B + t1 - t2 >= 0)
            ans.push(make_pair(t1 * 2 + t2, h));
    }
    cout << ans.top().first << " " << ans.top().second;
    return 0;
}
// *&)*@*

 

반응형

1. 높이 0부터 256까지 전체에 대해서 각각 높이별 소비 시간과 높이를 구합니다.
2. 그중 가장 시간이면서 가장 높은 높이를 갖는 항목이 정답이 됩니다.