풀이
주어진 영역 안에서 평탄화 작업을 실시하는데 가장 적은 시간을 갖는 높이와 그 시간을 출력하는 문제이다.
반복문을 통해 평탄화 기준이 되는 높이에 따라서 현재 영역에서 얼만큼의 변화가 필요한 지 찾아야한다.
각 좌표를 돌면서 제거될 블록과 필요한 블록의 갯수를 기준높이에 맞춰서 계산한 뒤 시간을 계산하면된다.
처음 파이썬으로 시도했을 때에는 시간 초과가 일어났다.
아무래도 최대 257 x 500 x 500 의 반복이 필요하기 때문에 약 6500만번의 연산이 필요하다.
파이썬은 1초에 약 2000만번의 연산이 가능하기 때문에 시간 초과가 나는건 당연한 것이다.
하지만 Pypy3 로 제출할 경우 시간초과없이 통과할 수 있다.
소스코드
import sys
input = sys.stdin.readline
n, m, b = map(int, input().split())
cord = [list(map(int, input().split())) for _ in range(n)]
ans = [999999999, 0]
for h in range(257): # 평탄화 높이
sub = 0 # 제거된 블록
add = 0 # 필요한 블록
for i in range(n):
for j in range(m):
if cord[i][j] > h:
sub += cord[i][j] - h
else:
add += h - cord[i][j]
if sub + b < add: # 제거하고 가지고있는 블록이 필요한 블록 보다 작을 경우
continue
t = sub*2 + add # 평탄화 시 걸리는 시간
if t <= ans[0]:
ans[0] = t
ans[1] = h
print(*ans)