아이디어 is null.. (실버2)

#18111번 마인크래프트 https://www.acmicpc.net/problem/18111

18111번: 마인크래프트

어떻게 구현해야하는지 떠오르지않아서 다른 자료들을 조금 참고했다.

 

브루트포스로 구현해야하는데, 탐색 높이의 범위를 설정하는 방법이 헷갈렸다.

탐색범위는 주어진 높이 중 최소높이부터 최대높이까지 진행하면 된다.

 

시간초과로 머리아팠지만 pypy3제출로 해결

파이썬으로 그리디 혹은 브루트포스를 제출하는건 늘 시간초과가 나는듯 하다.

 

from sys import stdin
input = stdin.readline
N, M, B = map(int, input().split())
maps = []
# 최솟값 초깃값은 가능한 수 중 가장 큰 값으로
# 최댓값 초깃값음 가능한 수 중 가장 작은값으로
minimum = 256
maximum = 0
# 입력을 받으면서 최솟값 최댓갑 설정
for _ in range(N):
    tmp = []
    for num in input().split():
        num = int(num)
        if num > maximum:
            maximum = num
        elif num < minimum:
            minimum = num
        tmp.append(num)
    maps.append(tmp)
    
    
# min - max 범위로 돌면서 해당 높이를 맞추는 시간을 체크한다.

# 최소 시간을 구해야한다.
# 가능한 가장 큰 값으로 초깃값 설정.
least_time = 256*500*500
height = 0
for h in range(minimum, maximum+1):
    plus, minus = 0, 0
    for x in range(N):
        for y in range(M):
            tmp = maps[x][y] - h
            if tmp > 0:  # 목표높이보다 현재높이가 더 높은경우
                minus += tmp  # 블럭 갯수를 더해줌
            elif tmp < 0:  # 목표높이보다 현재높이가 더 낮은경우
                plus -= tmp  # tmp 값이 음수이기 떄문에 뺄셈 진행

    if minus + B >= plus:  # 필요한 블럭을 가지고 있는지 확인
        time = minus*2 + plus  # 블럭을 제거하는 행위는 2초의 시간을 소모
        if time <= least_time:
            least_time = time
            height = max(height, h)

print(least_time, height)