풀이


주어진 영역 안에서 평탄화 작업을 실시하는데 가장 적은 시간을 갖는 높이와 그 시간을 출력하는 문제이다.

반복문을 통해 평탄화 기준이 되는 높이에 따라서 현재 영역에서 얼만큼의 변화가 필요한 지 찾아야한다.

각 좌표를 돌면서 제거될 블록과 필요한 블록의 갯수를 기준높이에 맞춰서 계산한 뒤 시간을 계산하면된다.

처음 파이썬으로 시도했을 때에는 시간 초과가 일어났다.

아무래도 최대 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)

References