문제 분석

이 문제는 마인크래프트에서 집을 짓기위해 땅을 골고루 펴야 하는 문제이다.
땅 크기는 주어지지않으며 n,m값을 입력받게해서 땅크기를 정해야한다.

땅 고르기 방법은 두 가지가 있다.
1. 인벤토리에서 땅을 채워서 평평하게 하는 방법.
2. 땅을 파서 평평하게 하는 방법.

이때 땅을 파게 된다면 파진 땅이 자신의 인벤토리에 들어간다.
그리고 1,2번 방법은 각각 1초와 2초가 걸린다.

땅 높이의 조건은 0~256이라고 했으니 이것을 이용해야한다.

땅 높이 검사하는 방법.

먼저 for문을 하나 만들고 시작을 제일 큰 높이인 256에서 부터 시작하는 것이다.
즉, 땅 행렬 nxm의 원소 하나하나를 256부터 시작하여 검사한다.
검사하는 방법은 256과 현재 땅 높이를 빼면 된다.

예시)

땅 높이가 아래와 같다면

0 0 0 0
0 0 0 0
0 0 0 1

0-256 0-256 0-256 0-256
0-256 0-256 0-256 0-256
0-256 0-256 0-256 1-256

이렇게 작동할 것이다.

알 수 있는 점

이렇게 해서 만약 0이 나왔다면 그 원소의 높이는 256인 최대 높이가 될 것이다.
양수가 나왔다면 최대 높이보다 크다는 것이다. 하지만 이 문제에서 최대 높이를 256으로 정의했기 때문에 양수가 나온다면 입력 값이 잘못된 것이다.

의문점

하지만 의문점이 하나 있다.
이 문제는 단순 땅을 평평하게 하는 것이 아닌 "최소 시간" 으로 땅을 평평하게 만들어야 한다.
그것을 이 문제에서 "목표높이"라고 명명했다. 그러면 이렇게 할시 어떻게 목표 높이를 알 수 있을까?

결론 부터 말하면 목표높이를 구하는 방법은 평균 높이를 구하면 된다.
예를 들어 높이가 이렇게 있었다고 해보자

64 64 64 48
64 37 64 64
59 64 64 63

이 땅을 가장 최소시간으로 똑같은 높이로 평평하게 해야한다.
위에서 목표높이는 평균 높이라 했으므로 (64 + 37) / 2 = 50.5 가 된다.
정수 처리를 하니 높이는 50이 된다.

코드에서는?

하지만 코드에서는 평균 높이를 구하는 문장이 없다. 그 이유는 어차피 최대 높이에서 -1씩 빼면서
계산을 하면 평균을 구하지 않아도 자동으로 가장 알맞는 높이를 찾을 수 있다.
즉, 최대 높이 (256)에서 0까지 모두 구한 후 가장 최소 시간이 걸리는 것을 고르는 것이다.
이렇게 하면 평균을 구해서 하는 것 보다 더 간결한 코드를 작성할 수 있다.

코드

n, m, b = map(int, input().split())

gd = [list(map(int, input().split()))for _ in range(n)]
INF = int(1e9)

# n과 m은 1부터 500으로 이 둘을 곱하면 25,000이다. 이는 파이썬 시간으로도 
# 충분히 커버가 가능하다. 
# 따라서 최대 최소를 만들지 않고 그냥 한다. 
# 다른 문제를 풀때 c, c++로는 풀리는데 파이썬으로 시간초과가 난다면 문제 조건을 다시 한번 잘 봐보자. 

# 검사하는 함수
# 받는 값은 땅(메트릭스), 층(레벨), b(인벤토리)로 한다. 
def ck(gd, lv, b):
    # 층마다 걸리는 시간을 리턴한다. 
    # 만약 불가능하다면 의미없는 값을 리턴하게 한다. 
    sc = 0 # 처음 시간을 0으로 초기화
    underB = 0 # 현재 층보다 아래에 위치한 블럭의 수

    for i in range(n):
        for j in range(m):
            z = gd[i][j] - lv
            if z > 0: # 만약 튀어 나와 있다면 0보다 클것이고 
                b += z # 튀어 나와있는 것들이 인벤토리에 들어간다. 
                sc += 2*z # 그리고 인벤토리에 들어가는 시간은 각 2초이다.
            else: # 아니라면 땅을 판다. 
                underB += -z
    if b < underB:
        return INF
    return sc + underB #여기에 초를 곱하지 않는 이유는 어차피 1초라서 블럭의 수로 대체 되기 때문이다. 


# 한층 한층 스캔하자. 
# n부터 m-1까지 하나씩 빼가면서 조사하는 것
# 하지만 이것을 for문으로 구현하려면 상당히 복잡해서 그냥 함수로 만들겠음

msc = INF
mlv = 0

for lv in range(256,-1,-1):
    sc = ck(gd, lv, b)

    if msc > sc:
        msc = sc
        mlv = lv
print(msc, mlv) 

설명

먼저 n,m,b를 받는다.
그런우 땅을 받아야 하는데 이것은 gd(ground)를 메트릭스로 받는다.
메트릭스로 받을때 리스트로 받게 하고 한줄로 여러번 입력 할 수 있게 받게 한다.

INF는 정수의 최대 크기를 지정하게 한다. 밑에서 msc라는 변수가 최소 시간을 나타내는데 처음에는 최소 시간을 알 수 없으니 무한대로 지정하고 최소값을 찾게 한다.

자세한 것은 주석에 달아놨다.