[백준] 18111번 마인크래프트 C++

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

C++

#include<iostream>
using namespace std;

// 땅 고루기 작업 세로 N, 가로 M
// 집터 맨 왼쪽 위의 좌표 (0,0)
// 좌표 (i,j)의 가장 위에 있는 블록 제거하여 인벤토리에 넣는다. 2초
// 인벤토리에서 블록 하나를 꺼내어 좌표 (i,j)의 가장 위에 있는 블록 위에 놓는다. 1초
// 땅 고르기 작업 걸리는 최소 시간과 그 경우 땅의 높이
// B개의 블록 들어있고, 땅의 높이 256보다 작거나 같은 자연수

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int Block[501][501];
    int n,m,b,T = 100000000, H = 0;
    cin >> n >> m >> b;

    // 1<=m,n <= 500 ,
    // i+2번 째 줄의 j+1번째 수는 좌표 (i,j)에서의 땅의 높이를 나타낸다.
    // 걸리는 시간과 땅의 높이 출력
    // 답이 여러 개 있으면 그중에서 땅의 높이가 가장 높은 것

    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            cin >> Block[i][j];
        }
    }

    for(int height = 0; height <= 256; height++) {
        int many = 0;
        int less = 0;

        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                if(height > Block[i][j]) { // 인벤토리에서 채워 넣어야함
                    many += height - Block[i][j];
                }
                else if(height < Block[i][j]) { // 뺴야함.
                    less += Block[i][j] - height;
                }
                else { // 같은 경우
                    continue;
                }
            }
        }

        // 빼는거랑 인벤토리 채워 넣는거랑 비교해야됨

        if(b + less >= many) {
            int time = less * 2 + many * 1;
            // 작업에 걸리는 최소 시간과 그 경우 땅의 높이를 출력
            // 땅의 높이가 가장 높은 것
            if(time <= T) {
                T = time;
                H = height;
            }
        }
    }
    cout << T << " " << H;
}

문제풀이

• 우선 최소 시간과 최대 높이를 구하는 것이기 때문에 최대 높이인 256까지 for문을 돌렸다. 그리고 for문 높이와 블럭이 채워져있는 높이를 비교하면서 for문 높이가 더 큰 경우는 인벤토리에서 채워 넣어야하는 경우, for문 높이가 더 작은 경우는 블럭을 빼야하는 경우로 나눴다. 그리고 블럭에서 뺀 개수 + 기존 인벤토리 안에 있던 블록이 인벤토리에 채워 넣어야하는 개수보다 큰 경우에 각 시간을 구해줬다. 그리고 최소 시간에 대한 최대 높이를 구하는 것이 문제이기 때문에 time <= T 해주면서 최소 시간에 대한 최대 높이를 구해줬다.

Comment

• 5번 정도 "틀렸습니다"가 나왔는데 계속해서 맨 마지막 if(time <= T)의 조건이 틀렸다고 생각했다. 하지만 T를 초기화한 값이 틀렸던 것이었다. 처음에는 1000000로 초기화했는데 이게 조건과 맞지 않았던 것이다. 그렇다면 T를 뭐로 초기화해야 맞는건지 궁금해졌다. 최대 격자 크기는 n = 500, m = 500으로 총 블록 개수 250,000개이고 땅 높이 차이는 최대 256이므로 256 2 = 512이다. 그렇다면 최악의 경우에 걸리는 시간은 512 250,000 = 128,000,000이다. 맨 처음 초기화한 값이 이것보다 작아서 계속해서 틀렸던 것이다....