boj 18111 마인크래프트 c++

boj 18111 마인크래프트 c++

 

 

처음엔 어떻게 풀지 감이 안 잡혀 다른 사람들의 코드를 참고하여 풀이 방법을 캐치했다.

기본적인 아이디어는 이렇다.

1. 정답의 후보가 될 수 있는 min~max를 돌면서
2. 해당 후보를 기준점(i)으로 맵 전체 요소 하나하나와 차이(i - map[j][k])를 구해서
3. 걸리는 시간을 체크하여 가장 작은 녀석을 캐치해낸다.
4. 가장 작은 녀석을 캐치해낼 때 제거할 횟수 + 인벤토리 내 아이템 갯수가 쌓을 횟수보다 같거나 큰지 확인한다.

 

정답 코드는 아래와 같다.

#include <bits/stdc++.h>
using namespace std;

int N, M; // N x M 너비의 땅
int board[500][500];
int B; // 인벤토리 내 블록 개수.

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

    // 가장 작은 값을 지정해야 하므로 INT_MAX 대입.
    int answerTime = INT_MAX;
    int answerHeight;

    int max = 0;
    int min = INT_MAX;

    cin >> N >> M >> B;
    // 하나씩 board에 넣으면서 min, max를 도출.
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            cin >> board[i][j];
            if (max < board[i][j])
                max = board[i][j];
            if (board[i][j] < min)
                min = board[i][j];
        }
    }

    // i를 정답이 되는 높이의 후보군이라고 생각하자.
    // min~max 사이에서 답이 나올 수밖에 없다.
    for (int i = min; i <= max; i++)
    {
        int build_time = 0; // 쌓아야 하는 횟수.
        int remove_time = 0; // 제거해야 하는 횟수.

        for (int j = 0; j < N; j++)
        {
            for (int k = 0; k < M; k++)
            {
                int temp = i - board[j][k];
                if (temp > 0)
                {
                    build_time += temp;
                }
                else
                {
                    remove_time += -temp;
                }
            }
        }

        if (remove_time + B >= build_time)
        {
            int tempTime = build_time + (2 * remove_time);
            // 과연 몇 층에서 가장 적은 시간이 걸릴 것이냐.
            if (tempTime <= answerTime)
            {
                answerTime = tempTime;
                answerHeight = i; // 해당 층의 높이.
                // i는 오름차순이므로 가장 높은 곳에서 해가 구해짐.
            }
        }
    }
    cout << answerTime << ' ' << answerHeight;
}

 

백준 18111 마인크래프트 cpp