[백준 18111] - 마인크래프트(구현) C++

문제

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

18111번: 마인크래프트

접근방법

최고점과 최저점을 저장한 후.

최고점에서 한 칸 제거하는 시간과 최저점에서 한 칸 추가하는 시간을 비교한다.

더 짧은 시간이 걸리는 쪽을 선택하고, 만약 최저점에서 추가할 블록이 없는 경우에는 무조건 최고점에서 한 칸 제거를 택한다.

코드

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <map>
#include <cmath>
#include <unordered_set>
#include <stack>

using namespace std;

#define FOR(i, n) for(int i=0;i<n;i++) 
#define FASTIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define MAX 987654321
#define MIN -987654321
int n, m, b;
int minute, height;   //답이 여러개라면 가장 높은 걸 선택. -> 삭제와 삽입의 시간이 같은 경우 삽입.
int under = MAX, upper = MIN;

int main() {
    FASTIO
    cin >> n >> m >> b;
    vector<vector<int>> ddang(n, vector<int>(m));
    FOR(i, n) FOR(j, m) {
        cin >> ddang[i][j];
        upper = max(upper, ddang[i][j]);
        under = min(under, ddang[i][j]);
    }
    while(upper != under) {
        //upper는 한칸 내리는 시간과
        //under 한칸 올리는 시간을 비교
        //다만 under올릴 때는 블록이 그만큼 있는 지 세봐야함.
        int timeA = 0, timeB = 0;
        FOR(i, n) FOR(j, m) {
            if (ddang[i][j] == upper) timeA += 2;
            if (ddang[i][j] == under) timeB += 1;
        }
        //timeB가 가진 블록보다 작거나 같고, A보다 시간이 덜 걸리거나 같은 경우.
        if (timeB <= b && timeB <= timeA) {
            FOR(i, n) FOR(j, m) {
                if (ddang[i][j] == under) ddang[i][j]++;
            }
            b -= timeB;
            minute += timeB;
            under++;
        } else {
            FOR(i, n) FOR(j, m) if (ddang[i][j] == upper) ddang[i][j]--;
            minute += timeA;
            upper--;
            b += (timeA / 2);
        }
    }
    cout << minute << " " << upper << endl;



    return 0;
}

개선할 점

최고점에서 한 칸씩 제거할 때마다 가지고 있는 블록의 개수를 추가해줘야 하는데, 그 작업을 잊어서 한 번 틀렸다.

 

한번 테스트 케이스를 돌려보고 제출했으면 안 틀렸을 수 있는 문제였는데 아쉽다.

 

이래서 테스트케이스 만들어보는 것이 중요하다.