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

문제 링크

처음에는 500x500 크기의 Map을 이용하려고 했는데,
맵의 넓이가 훨씬 넓어진다면(height와 width는 500 이내라는 조건이 있지만 그냥 어렵게 풀어보고 싶었다) 비효율적일 수 있다는 생각에 counting array를 사용해 보았다.

사실 이 방법도 맵의 최대 고도만큼의 크기를 가지는 배열을 선언하기 때문에 최대 고도가 훨씬 높아질 수 있다면 비효율적일 수 있지만 그것까진 고려하지 않았다😅

처음에는 입력을 받은 뒤에 계속 무한루프가 발생했다.
for (unsigned int tempAltitude = maxAltitude; (tempAltitude + 1) >= (minAltitude + 1); tempAltitude--)
이 부분이 문제였는데, 처음에는 for (unsigned int tempAltitude = maxAltitude; tempAltitude >= minAltitude; tempAltitude--) 이렇게 작성하였다.

tempAltitude의 데이터 타입이 unsigned int이기 때문에 항상 0 이상일 수밖에 없는데, 이 때문에 최저 고도가 0일 때 무한루프가 발생한다.
tempAltitude >= minAltitude가 항상 true이기 때문이다.

resultTime의 초기값이 height * width * 512인 이유는 가능한 최대 시간이 height * width * 512이기 때문이다. 해당 시간은 모든 구역의 고도가 가능한 최대 고도인 256이고, 모든 구역을 파내서 고도를 0으로 만드는 데 걸리는 시간이다.

가장 효율적인 방식은 아닌 것 같아 슬프다🥲
나중에 CPP 마스터가 되어서 다시 깔끔한 로직으로 고쳐봐야겠다는 생각을 하면서 이만 총총..🦘

#include <iostream>
#include <vector>
#include <numeric>

#define MAX_ALTITUDE 256
#define MIN_ALTITUDE 0

bool isPossible(unsigned int havingBlocks, unsigned int areaToBeFilled, unsigned int areaToBeDug) {
    if (areaToBeDug + havingBlocks < areaToBeFilled) {
        return false;
    } else {
        return true;
    }
}

unsigned int calculateTime(unsigned int areaToBeFilled, unsigned int areaToBeDug) {
    return areaToBeFilled + (areaToBeDug * 2);
}

std::pair<unsigned int, unsigned int> findAreas(unsigned int *arr, unsigned int startIndex, unsigned int endIndex, unsigned int tempAltitude) {
    unsigned int AreaToBeFilled = 0, AreaToBeDug = 0;
    for (unsigned int i = startIndex; i <= endIndex; i++) {
        if (i > tempAltitude) {
            AreaToBeDug += ((i - tempAltitude) * arr[i]);
        } else if (i < tempAltitude) {
            AreaToBeFilled += ((tempAltitude - i) * arr[i]);
        }
    }

    return std::make_pair(AreaToBeFilled, AreaToBeDug);
}

int main(void) {
    // Sync off
    std::ios_base::sync_with_stdio(false);

    unsigned int height, width, numberOfHavingBlocks;
    unsigned int altitude, altitudeCountArr[MAX_ALTITUDE + 1] = {0, };
    unsigned int minAltitude = MAX_ALTITUDE, maxAltitude = MIN_ALTITUDE;
    std::pair<unsigned int, unsigned int> AreaPair;

    std::cin >> height >> width >> numberOfHavingBlocks;

    unsigned int resultTime = height * width * 512, resultAltitude = 0;

    for (unsigned int i = 0; i < height; i++) {

        for(unsigned j = 0; j < width; j++) {
            std::cin >> altitude;

            altitudeCountArr[altitude] += 1;

            if (altitude < minAltitude) {
                minAltitude = altitude;
            }

            if (altitude > maxAltitude) {
                maxAltitude = altitude;
            }

        }        
    }

    for (unsigned int tempAltitude = maxAltitude; (tempAltitude + 1) >= (minAltitude + 1); tempAltitude--) {
        AreaPair = findAreas(altitudeCountArr, minAltitude, maxAltitude, tempAltitude);
        if (isPossible(numberOfHavingBlocks, AreaPair.first, AreaPair.second)) {
            unsigned int tempTime = calculateTime(AreaPair.first, AreaPair.second);
            if ((resultTime > tempTime) || ((resultTime == tempTime) && (resultAltitude < tempAltitude))) {
                resultTime = tempTime;
                resultAltitude = tempAltitude;
            }
        }
    }

    std::cout << resultTime << ' ' << resultAltitude << std::endl;

    return 0;
}

참고로 코드의 시간복잡도는 O(height * width * 256)이다.