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

백준 - 18111

---

풀이

256 ~ 0까지 모든 높이의 평지를 만들어보며 최단 시간을 구하는 문제이다.

동일한 층의 개수를 배열로 입력받았고, 가장 높은 층을 구했다.

최단시간이 동일하다면, 높이가 가장 높은 것을 출력해야 하기 때문에 256부터 0으로 내려가면서 탐색했다.

(만약 시간이 동일하다면 높은 층의 기록이 유지되므로)

최대 시간(result)은 다음과 같다.

땅의 크기(500 x 500) x  설치(2) x 최대높이(256) = 128,000,000

---

소스코드

#include <stdio.h>
int main(){
    int N, M, B, arr[257] = {0, }, temp, max = 0;
    scanf("%d %d %d", &N, &M, &B);
    for (int i = 0; i < N*M; i++){
        scanf("%d", &temp);
        arr[temp]++;
        max < temp && (max = temp);
    }
    int result = 128000000, height;
    for (int flatLand = max; flatLand >= 0; flatLand--){
        int set = 0, remove = 0;
        for (int i = 0; i < 257; i++)
            if (arr[i])
                if (i < flatLand)
                    set += arr[i]*(flatLand-i);
                else if (i > flatLand)
                    remove += arr[i]*(i-flatLand);
                
        int time = set + remove*2;
        int inventory = B + remove - set;
        if (time < result && inventory >= 0){
            height = flatLand;
            result = time;	
        }
    }
    printf("%d %d\n", result, height);
}

---

출처

18111번: 마인크래프트