#18111

첫 번째 풀이

N, M, B = map(int, input().split())
inputMap = [list(map(int, input().split())) for i in range(N)]
# print(inputMap)
nowBlock = 0 

# answerList = []

def plusProcessFunc ( row, col, hei, block):
    if inputMap[row][col] > hei:
        block += (inputMap[row][col] - hei)
        return 2*(inputMap[row][col] - hei)
    else:
        return 0

def minusProcessFunc ( row, col, hei, block):
    if inputMap[row][col] < hei:
        block -= (hei - inputMap[row][col])

        if block < 0:
            return -1

        else:
            return (hei - inputMap[row][col])
    else:
        return 0

answerHeight = 10e9
answerTime = 10e9

for height in range( 256, -1, -1 ):
    totalTime = 0
    nowState = False
    nowBlock = B

    # 높이가 더 높은 블럭 쟁여두기
    for i in range(N):
        for j in range(M):
            if inputMap[i][j] == height:
                pass
            else:
                # if height == 2:
                #     print("i = ", i, "j = ", j)
                totalTime += plusProcessFunc(i, j, height, nowBlock)

    # if height == 2:
    #     print("totalTime = ", totalTime)

    # 높이가 더 낮은 블럭 채우기
    for i in range(N):
        for j in range(M):
            if inputMap[i][j] == height:
                pass
            else:
                resultFunc = minusProcessFunc(i, j, height, nowBlock)
                if resultFunc == -1:
                    nowState = True
                    break
                
                else:
                    totalTime += resultFunc
        if nowState == True:
            break

    # if height == 2:
        # print("totalTime = ", totalTime)

    if nowState == True:
        continue

    # print("Height = ", height, "totalTime = ", totalTime)

   
    if totalTime < answerTime:
        answerTime = totalTime
        answerHeight = height
        
    if totalTime == answerTime and answerHeight < height:
        answerHeight = height
        # if height == 2:
        #     print(totalTime)

        # answerList.append([totalTime, height])
        
print(answerTime, answerHeight)
# print(answerList)

높이가 최대 256 이기 때문에 -1 을 해가면서 해당 높이를 채우기 위해 필요한 시간을 체크한다. 블럭을 넣고 빼주는 시간만 체크하면 되기 때문에 직접 매트릭스를 수정하지 않아도 된다 (이게 핵심이라고 생각했다)

시간이 같을 때 (정답이 여러 개가 나올 수 있을 때) 높이가 높은 경우를 채택해야 한다. 이 조건을 놓치고 있어서 삽질하다가 병우형이 가르쳐줬다.

주어진 테스트 케이스도 다 맞고 위의 조건도 추가해줬다. 그거에 대해 만든 예제도 통과했다. 도대체 뭐가 틀렸는지를 모르겠다.

pypy3 => 틀렸습니다
python 3 => 시간 초과

뭔가 잘못됐다.

답지 살짝 보고 다시 트라이

굳이 함수를 나눠서 각각에 대해 수행을 할 필요가 없다. 위에 적은 대로 시간만 체크하면 되기 때문이다.

두 번째

import sys

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

answerTime = 10e9
answerHeight = 10e9

for height in range( 257 ):
    # 시간이 같을 때는 높이가 높은 순으로 출력하라는 조건에 맞게
    # for i in range(257)은 항상 i가 오름차순으로 돌기 때문에
    # 시간이 같아도 최종적으로는 높이가 높은 순으로 나오게 된다

    # 내 처음 풀이는 256에서 -1 하면서 0까지 계산했음

    totalTime = 0
    block = B

    # 높이가 더 높은 블럭 쟁여두기
    for i in range(N):
        for j in range(M):

            if height < inputMap[i][j]:
                # 블록 높이가 정해진 높이보다 높을 때  => 블록 빼줘야 해
                totalTime += 2 * (inputMap[i][j] - height)
                block += (inputMap[i][j] - height)

            if height > inputMap[i][j]:
                # 블록 높이가 정해진 높이보다 낮을 때 => 블록 쌓아야 해
                totalTime += (height - inputMap[i][j])
                block -= (height - inputMap[i][j])
    
    if block < 0:
        continue
    
    if totalTime <= answerTime:
        answerTime = totalTime
        answerHeight = height
    
print(answerTime, answerHeight)
# print(answerList)

=> 시간초과

if 2번으로 각각의 상황을 비교할 필요가 없다.
=> if else로 대체
=> 통과

정답 코드

N, M, B = map(int, input().split())
inputMap = [list(map(int, input().split())) for i in range(N)]

answerTime = 10e9
answerHeight = 0

for height in range( 257 ):
    totalTime = 0
    minusVal = 0
    plusVal = 0

    for i in range(N):
        for j in range(M):
            if height < inputMap[i][j]:
                minusVal += inputMap[i][j] - height

            else:
                plusVal += height - inputMap[i][j]
    
    if minusVal + B < plusVal:
        continue

    totalTime = 2 * minusVal + plusVal

    if totalTime <= answerTime:
        answerTime = totalTime
        answerHeight = height
    
print(answerTime, answerHeight)

파이썬은 언어 특성상 시간 초과에 되게 민감하다 한줄로 통과, 시간초과가 왔다 갔다 한다.
바로 다음 글에 이 뭣같은 시간 초과가 날 수 있는? 선에 아슬아슬하게 걸려있는 조건들에 대해 정리해보려고 한다.