[Algorithm] Baekjoon 18111번 : 마인크래프트

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

18111번: 마인크래프트

int n, m, b;
int arr[500][500] = { 0 };
 
int main(void)
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    cin >> n >> m >> b;
 
    for (int i = 0; i < n; ++i)
    {
         for (int j = 0; j < m; ++j)
        {
            cin >> arr[i][j];
        }
    }
 
    int answerTime = 0x3f3f3f3f;
    int answerHeight = 0;
 
    for (int height = 0; height <= 256; ++height)
    {
        if (height == 256)
        {
            int asdf = 0;
        }
        int blockCount = b; // 가지고 있는 블럭개수
        int buildingCount = 0; // 블럭을 쌓아올린 횟수.
        int removeCount = 0; // 블럭을 제거한 횟수.
 
        for (int i = 0; i < n; ++i)
        {
            for (int j = 0; j < m; ++j)
            {
                if (arr[i][j] > height) // 블럭 제거해야하면
                {
                    blockCount += arr[i][j] - height;
                    removeCount += arr[i][j] - height;
                }
                else if(arr[i][j] < height) // 블럭을 쌓아야하면
                {
                    blockCount -= height - arr[i][j];
                    buildingCount += height - arr[i][j];
                }
            }
        }
 
        if (blockCount < 0) continue;
        else
        {
            int time = removeCount * 2 + buildingCount;
            if (time <= answerTime)
            {
                answerTime = time;
                answerHeight = max(answerHeight, height);
            }
        }
    }
 
    cout << answerTime << ' ' << answerHeight;
}
 

파라매트릭 서치의 느낌을 가지고있는 완전탐색문제이다.

완전탐색을 돌려해도 무언가 '기준'이 있어야 시간이 오래걸리더라도 탐색을 하던가 말던가 할 수 있다.

그것에 대한 기준을 '높이'로 잡아버려서 해결한다.

즉 해당 높이로 평평하게 만들수있는지 없는지에 대한 검사 후, 만들 수 있으면 정답을 업데이트하면 된다.