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

📖 문제

 

📋 코드

#include <iostream>
#include <algorithm>
using namespace std;

#define MAX_TIME 640000000 // 최대 시간
int N, M, B, x;
int blocks[256 + 1];
int ans[2];
int main()
{
    // freopen("input.txt", "r", stdin);
    cin >> N >> M >> B;

    int total = 0;
    // 높이별 블럭 수 기록
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            cin >> x;
            total += x;
            for (int k = 1; k <= x; k++)
                blocks[k]++;
        }
    }

    ans[0] = MAX_TIME;

    for (int i = 0; i <= 256; i++)
    {
        int time = 0;      // 시간
        int height = i;    // 기준 높이
        int inventory = B; // 인벤토리에 있는 블럭 수

        // 채우기
        for (int j = 1; j <= i; j++)
        {
            inventory -= N * M - blocks[j];
            time += N * M - blocks[j];
        }

        // 고르기
        for (int j = i + 1; j <= 256; j++)
        {
            inventory += blocks[j];
            time += blocks[j] * 2;
        }
        if (inventory < 0)
            break;

        if (ans[0] >= time)
        {
            ans[0] = time;
            ans[1] = height;
        }
    }

    cout << ans[0] << " " << ans[1] << '\n';
}

👨🏻‍💻 결과

 

 

📕 풀이 방법

브루트 포스 방식으로 높이(0부터 256까지) i 기준으로 땅을 고르고 (비어있는 부분은 채우고 기준 높이보다 높이 있는 블록들은 제거) 최소 시간이 갱신되면 업데이트하여 ans 배열에 저장하도록 하였습니다.

그리고 문제의 조건 중에서 "답이 여러 개일 시 땅의 높이가 가장 높은 것을 출력" 하라고 하였으므로

if (ans[0] >= time)
{
    ans[0] = time;
    ans[1] = height;
}

'>'가 아닌 '>='으로 시간이 같을 때 높이를 업데이트해주어야 합니다.
(요거 때문에 왜 틀리나 엄청 고민했네요....) 

 

 

🔗 링크

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

18111번: 마인크래프트