from sys import stdin
stin = stdin.readline
h, w, blocks = map(int, stin().split()) # 가로 세로 인벤블록 수
ground = [list(map(int, stin().split())) for _ in range(h)] # 지형정보

min_height = min(map(min, ground))
max_height = min(256, max(map(max, ground)))

min_time = float('inf')
result_height = 0

for target_level in range(min_height, max_height + 1):
    blocks2del = 0
    blocks2add = 0
    for y in range(h):
        for x in range(w):
            if ground[y][x] > target_level: #땅이 높으면
                blocks2del += ground[y][x] - target_level
            elif ground[y][x] < target_level: #땅이 낮으면
                blocks2add += target_level - ground[y][x]

    if blocks2del + blocks >= blocks2add: #메울 수 있으면
        time = 2 * blocks2del + blocks2add #시간계산
        if time <= min_time: #시간이 최단시간이랑 같거나 작으면 업데이트
            min_time = time  
            result_height = target_level# 시간이 같아도 나중에 나온 높이 저장

print(min_time, result_height)

시간초과가 뜹니다.

주어진 코드에서 시간 초과가 발생하는 원인은 주로 두 가지 요소 때문입니다:

1. 중첩 반복문: 코드에는 두 개의 중첩 반복문이 있습니다. 하나는 가능한 모든 높이를 순회하는 반복문이고(for target_level in range(min_height, max_height + 1):), 다른 하나는 집터의 모든 위치를 순회하는 반복문입니다(for y in range(h): 내부의 for x in range(w):). 이 중첩 반복문은 모든 높이와 모든 위치에 대해 계산을 수행하므로, 입력 크기가 커질수록 계산량이 기하급수적으로 증가합니다.
2. 높이 범위: 가능한 높이의 범위가 넓을 수 있습니다. 최소 높이부터 최대 높이(최대 256)까지 모든 정수에 대해 검사를 수행합니다. 이는 최악의 경우 256회의 반복을 의미할 수 있으며, 각 반복마다 N*M 크기의 집터를 순회합니다.

시간 복잡도 분석

• 높이를 순회하는 반복문: 최악의 경우 256회 반복
• 집터의 모든 위치를 순회하는 중첩 반복문: N*M 회 반복
• 따라서, 전체 시간 복잡도는 대략 **O(256*N*M)**이 됩니다.

시간 초과 해결 방법

• 효율적인 알고리즘: 중첩 반복문을 줄이거나, 필요 없는 계산을 제거하는 등의 방법으로 알고리즘의 효율성을 개선해야 합니다. 예를 들어, 미리 땅의 높이별로 블록의 총 개수를 계산해 놓고, 그 정보를 바탕으로 필요한 추가/제거 블록 수를 더 빠르게 계산할 수 있습니다.
• 데이터 구조 최적화: 특정 데이터 구조를 사용하여 블록의 추가 및 제거에 필요한 정보를 더 효율적으로 관리할 수 있습니다. 예를 들어, 높이별 블록 수를 관리하는 배열을 사용할 수 있습니다.

이러한 최적화를 통해 시간 복잡도를 개선하고, 주어진 시간 제한 내에 문제를 해결할 수 있습니다.

높이별 블록 수를 관리하는 배열을 사용하여 문제를 해결하기 위해 다음과 같은 접근 방식을 사용할 수 있습니다:

1. 높이별 블록 수 계산: 집터의 각 좌표를 순회하며 해당 높이의 블록 수를 셉니다. 이를 위해 높이를 인덱스로 하는 배열을 사용하여, 각 높이에 해당하는 블록 수를 저장합니다.
2. 높이 조정 비용 계산: 각 목표 높이에 대해 땅을 고르는 데 필요한 작업(블록 추가 또는 제거)의 비용을 계산합니다. 블록을 제거할 때와 추가할 때의 시간 비용(각각 2초와 1초)을 고려해야 합니다.
3. 최소 시간과 최적 높이 찾기: 모든 가능한 높이에 대해 계산된 비용 중 최소 비용을 찾고, 그 때의 높이를 최적 높이로 선택합니다. 시간 비용이 같은 경우 더 높은 높이를 선택합니다.

다음은 이러한 접근 방식을 구현한 코드입니다:

N, M, B = map(int, input().split())  # 집터의 크기와 인벤토리에 있는 블록 수
ground = [list(map(int, input().split())) for _ in range(N)]  # 땅의 높이 정보

# 높이별 블록 수를 계산
height_counts = [0] * 257
for row in ground:
    for height in row:
        height_counts[height] += 1

min_time = float('inf')
result_height = 0

# 각 높이에 대해 필요한 작업 비용 계산
for target_height in range(257):
    blocks2add = blocks2del = 0
    for height in range(257):
        if height < target_height:
            blocks2add += (target_height - height) * height_counts[height]
        elif height > target_height:
            blocks2del += (height - target_height) * height_counts[height]

    # 현재 인벤토리의 블록으로 조정 가능한지 확인
    if blocks2del + B >= blocks2add:
        time = 2 * blocks2del + blocks2add
        # 최소 시간과 최적 높이 업데이트
        if time <= min_time:
            min_time = time
            result_height = target_height

print(min_time, result_height)