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

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

18111번: 마인크래프트

• 이 문제를 보고 처음엔 이분탐색으로 풀어야겠다고 생각했다.
• 근데 이분탐색을 사용하려면 mid 값이 줄어들거나 늘어나야하는 기준이 있어야 하는데 그 기준을 뭐로 두기에는 애매했다.
• 그래서 일단 높이의 Min 값과 Max값을 찾고 그 range를 그 범위 만큼 돌려주면서 각각 높이들을 비교해서 어떤게 시간이 적게 걸리는지 비교해서 갱신해주는 방식을 사용하였다.
• 여기서 내가 실수를 계속 한 부분은 구한 h가 음수일 때 pluscnt(쌓아야하는 블럭수)에 계속 더해주니까 음수값이 나왔었는데 이 부분에서 시간을 많이 썼다. 음수값이니까 pluscnt값을 구해주려면 빼줘야한다.

import sys
input = sys.stdin.readline

n,m,b = map(int,input().split())
graph = []
for _ in range(n):
    graph.append(list(map(int,input().split())))


#중간값을 구성
Min = min(map(min,graph))
Max = max(map(max,graph))
leastTime = 1e9

for i in range(Min,Max+1):
    pluscnt = 0
    minuscnt = 0
    for j in range(n):
        for k in range(m):
            h = graph[j][k] - i
            if h>0:
                #minuscnt = 1번 작업 수
                minuscnt += h
            elif h<0:
                #h가 음수니까 -를 취해줌으로써 더하기로 바꿔준다.
                #pluscnt = 2번 작업 수
                pluscnt -= h
    if minuscnt+b>=pluscnt:
        time = minuscnt*2 + pluscnt
        #계속 비교해주면서 최솟값을 찾는다.
        if leastTime >= time:
            leastTime = time
            resultHeight = i
print(leastTime,resultHeight)