/<> 백준 18111번 : 마인크래프트 (C언어)

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

 

 

노가다를 통해 최소 시간과 블록의 높이를 구하는 브루트포스 문제입니다.(변수가 은근히 많아 이름을 쓸 때 헷갈렸습니다..;) 별 다른 알고리즘을 쓰지 않아 문제 자체는 풀기 괜찮았습니다.

 

 

1. 입력받은 땅의 최고 높이와 최저 높이를 구합니다. 평탄화가 끝난 뒤 땅의 높이는 이 둘 사이의 값입니다.

 

2. 최대 높이와 최소 높이 사이에서 반복문을 통해 한 높이를 목표로 평탄화를 할 때, 쌓아야 하는 블록 개수와 파내야 하는 블록 개수를 구합니다.

 

3. 쌓아야 하는 블록 개수가 <파내야 하는 블록 개수 + 인벤토리의 블록 개수>보다 많으면 해당 높이론 평탄화를 하지 못하므로 생략합니다.

 

4. 평탄화에 걸린 시간의 최솟값과 해당 높이를 구합니다. 시간이 같을 경우 높이가 더 높은 경우를 출력합니다.

 

 

<코드>

#include <stdio.h>
#include <stdlib.h>

int n, m, b;
int field[500][500] = {0,};

int main() {
    scanf("%d %d %d", &n, &m, &b);
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) scanf("%d", &field[i][j]);
    }
    
    int min_h = 256, max_h = 0;
    for(int u = 0; u < n; u++) {
        for(int v = 0; v < m; v++) {
            if(min_h > field[u][v]) min_h = field[u][v];
            if(max_h < field[u][v]) max_h = field[u][v];
        }
    }
    
    int min_time = 0, max_height = 0;
    
    for(int k = max_h; k >= min_h; k--) {
        int need_up = 0, need_down = 0;
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                if(field[i][j] > k) need_down += field[i][j] - k;
                else if(field[i][j] < k) need_up += k - field[i][j];
            }
        }
        
        if(need_up > need_down + b) continue;
        
        int time = need_up + need_down*2;
        
        if(min_time == 0) {
            min_time = time;
            max_height = k;
        }
        else if(min_time > time) {
            min_time = time;
            max_height = k;
        }
        else if(min_time == time) {
            if(max_height < k) max_height = k;
        }
    }
    
    printf("%d %d\n", min_time, max_height);
    return 0;
}