[백준, Python] 18111 마인크래프트

가장 먼저, 땅의 높의는 256을 초과할 수 없으므로 높이의 최대값은 256 입니다. 

또한, 가로 세로는 500 이하이므로 높이, 가로, 세로 3중 포문을 돌려도 256 * 500 * 500 = 64,000,000

즉, 1초 안에 가능합니다. 따라서 브루트 포스로 풀 수 있습니다. 

 

핵심 아이디어는 다음과 같습니다. 

- for문을 통해 256층까지 탐색하면서 각 층의 블록들의 초과분과 부족분을 찾습니다. 

- (초과분 + 인벤토리의 블럭 수) >= 부족분 이면, 그 층 개수만큼의 블럭으로 평탄하게 할 수 있는 것입니다. 

- 따라서, 부족분과 초과분을 이용하여 시간을 계산하고 min값을 for문을 돌면서 체크합니다. 

- 층 수와 min값을 출력합니다.  

import sys

n, m, b = list(map(int, input().split()))
graph = [list(map(int, input().split())) for _ in range(n)]
idx = 0
answer = sys.maxsize

for floor in range(257):
    max_block, min_block = 0, 0  # 초과분, 부족분

    for i in range(n):
        for j in range(m):
            if graph[i][j] >= floor:  # 초과분 계산
                max_block += graph[i][j] - floor
            else:  # 부족분 계산
                min_block += floor - graph[i][j]

    if (max_block + b) >= min_block:  # floor층 개수로 평탄하게 할 수 있는지 체크(초과분 + 인벤토리의 블럭 수가 부족분보다 많으면 평탄하게 가능)
        if max_block * 2 + min_block <= answer:
            answer = max_block * 2 + min_block
            idx = floor  # 층수
print(answer, idx)