Algorithms | 백준 18111 마인크래프트

Date

2025/04/12

1. 코드

#include <iostream>
#include <algorithm>

int g_heightFreq[257] = {};
int g_numRows = 0;
int g_numCols = 0;
int g_numBlocks = 0;

int CalculateTime(int p_height)
{
    int time = 0;
    int numBlocks = g_numBlocks;

    for (int height = 0; height <= 256; ++height)
    {
        const int freq = g_heightFreq[height];
        int diff = height - p_height;

        // 제거
        if (diff > 0)
        {
            time += 2 * diff * freq;
            numBlocks += diff * freq;
        }
        // 설치
        else if (diff < 0)
        {
            time -= diff * freq;
            numBlocks += diff * freq;
        }
    }

    return (numBlocks < 0) ? -1 : time;
}

int main()
{
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);

    std::cin >> g_numRows >> g_numCols >> g_numBlocks;
    int maxHeight = 0;
    int minHeight = 256;

    // 높이 정보 기록
    for (int i = 0; i < g_numRows * g_numCols; ++i)
    {
        int height;
        std::cin >> height;
        ++g_heightFreq[height];

        maxHeight = std::max(maxHeight, height);
        minHeight = std::min(minHeight, height);
    }

    int minTime = 500 * 500 * 256 * 2;
    int optimalHeight = 0;

    // 최소/최대 높이 범위의 땅 고르기 작업 시 걸리는 시간 계산
    for (int h = maxHeight; h >= minHeight; --h)
    {
        const int time = CalculateTime(h);

        // 블록이 부족한 경우
        if (time == -1)
        {
            continue;
        }
        // 기존 작업 시간보다 더 짧은 경우
        if (time < minTime)
        {
            minTime = time;
            optimalHeight = h;
        }
    }

    std::cout << minTime << " " << optimalHeight;

    return 0;
}
C++
복사

2. 분석

처음엔 parametric search 문제인줄 알았습니다. 땅 고르기 높이가 올라갈 수록, 작업 시간이 감소할 것이라고 예상했습니다. 만약 작업 시간이 정말 이런 단조 감소 함수라면, parametric search로 접근해서 해결할 수 있을 것 입니다. 하지만 땅 고르기 높이가 올라간다고 해서 작업 시간이 반드시 줄어들지 않습니다. 반례를 몇 가지 생각해볼 수도 있겠지만 문제에 이미 힌트가 있습니다. 문제 설명 중 작업 시간이 같을 시 높이가 더 높은 경우를 출력하라고 나와 있습니다. 이 문구에서 땅 고르기 높이가 올라간다고 해서 작업 시간이 반드시 줄어드는 것이 아니라는 것을 어느 정도 암시하고 있습니다. parametric search로 접근하지 못 한다는 것을 깨닫고 brute-force로 접근했습니다. brute-force도 처음에는 비효율적으로 접근했는데, CalculateTime 과정에서 맵의 모든 좌표를 순회하는 방식으로 시간을 계산했습니다. 이런 식이면 최악의 경우 맵이 500 * 500 크기일 때, CalculateTime 호출 시 250’000번의 반복이 발생합니다. 이 문제를 해결하고 개선한 최종 코드가 현재 코드입니다. CalculateTime에서 모든 좌표를 순회하는 방식이 아닌, 0~256까지 높이에 대해 각 높이에 해당하는 좌표의 개수를 활용하여 작업 시간을 계산합니다. 이때는 맵 크기에 무관하게 항상 257번의 반복만 합니다. 최종 코드의 시간 복잡도를 계산하겠습니다. 모든 높이에 해당하는 좌표의 개수를 기록할 때 O(M * N), 땅 고르기의 최소 작업 시간을 찾을 때 O((maxHeight - minHeight) * 257) 이므로, O(M * N + (maxHeight - minHeight) * 257)이 최종 시간 복잡도가 됩니다.