[백준] 18111 - 마인크래프트 [Python(파이썬)]

문제

www.acmicpc.net/problem/18111

18111번: 마인크래프트

 

풀이

재밌어 보이는 문제라서 풀어보았다.

3중 for문을 이용해서 땅의 최소 높이(0)부터 최대 높이(256)까지 모두 검사해본다.

 

이때, B + sum(g[i][j])  // m*n을 X라 하면, 땅의 최대 높이는 min(256, X)이 된다. → B가 최대 6.4 × 10^7가 될 수 있기 때문에 X가 기하급수적으로 커질 수 있다!

• B: 인벤토리에서 가지고 있는 블록의 개수
• sum(g[i][j]): 각 좌표 별 땅의 높이의 합 (i→n, j→m)

이를 이용하여 for문의 범위를 좁히는 방식으로 최적화를 할 수 있다.

 

코드

import sys

def flatten(h):
    time = 0
    for i in range(n):
        for j in range(m):
            if g[i][j] == h:
                continue
            elif g[i][j] > h:
                time += (2 * (g[i][j] - h))
            else:
                time += (h- g[i][j])
    return [time, h]

n, m, b = map(int, sys.stdin.readline().split())
g = [[int(x) for x in sys.stdin.readline().split()] for _ in range(n)]
result = [float('inf'), 0]
_sum = b

for i in range(n):
    for j in range(m):
        _sum += g[i][j]

_max = min(257, _sum//(n*m) + 1)

for h in range(0, _max):
    time, height = flatten(h)
    if time <= result[0]:
        result[0] = time
        if height > result[1]:
            result[1] = height

print(*result)