백준 18111 마인크래프트

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

18111번: 마인크래프트

일단 땅고르기를 위해 가장 최소의 시간을 구하기 위해서는 여러 방법이 있었다.

 

1. ground 2차원 배열에서 중간값을 찾아서 그 중간값을 기준으로 잡고 땅고르기를 하기(이분탐색)

ground의 min값 ~ max값 사이의 range를 돌면서 그때 해당하는 조건에 대해서 테스트하는것도 좋은 방법

n, m, b = list(map(int, input().split()))

ground = [list(map(int, input().split())) for _ in range(n)]

from math import inf
res = inf
height = 0
start = min(map(min,ground))
end =  max(map(max,ground))

for h in range(start, end + 1):
    max_value = 0
    min_value = 0
    for i in range(n):
        for j in range(m):
            if ground[i][j] > h:
                max_value += (ground[i][j] - h)
            else:
                min_value += (h - ground[i][j])
    bag = max_value + b

    if bag < min_value:
        continue

    time = 2 * max_value + min_value

    if time <= res:
        res = time
        height = h
print(res, height)

 

2. 0 ~ 256의 높이를 모두 고려한다음에 가장 작은 값을 구하기(완전탐색)

from math import inf
import sys

N, M, B = map(int, input().split())
ground = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]

tall = 0
ans = inf

for i in range(257):
    max = 0
    min = 0
    for j in range(N):
        for k in range(M):
            if ground[j][k] < i:
                min += (i - ground[j][k])  # 현재 높이가 블록 높이보다 높을 때 (min 만큼 인벤토리에서 꺼내서 채워야 함)
            else:
                max += (ground[j][k] - i)  # 블록 높이가 현재 높이보다 높을 때 (max 만큼 블록이 제거 후 인벤토리에 들어감)

    inventory = max + B

    if inventory < min:
        continue

    time = 2 * max + min

    if time <= ans:
        ans = time
        tall = i

print(ans, tall)