[Python] 백준 18111번: 마인크래프트

풀이 전략은 다음과 같습니다.

땅 높이의 범위가 0~256으로 명시되어 있기 때문에 활용해보겠습니다.
땅의 높이가 k일 때의 소요 시간을 time[k] 에 저장합니다.
또한 현재까지 소요 시간이 가장 작은 땅의 높이를 height에 저장합니다.

1. for문으로 g를 0에서 256까지 순회합니다. 이 때, g는 현재의 땅 높이가 됩니다.
2. 각 땅 높이마다 인벤토리에 남은 블록 수를 계산해줘야겠죠?
   이를 local 변수인 block에 저장하겠습니다. block은 B로 초기화해줍니다.
3. 내부에서는 for문으로 집터를 순회하면서
   땅 높이보다 낮으면 블록을 채워주고, 높으면 블록을 빼줍니다.
   이 때 시간도 같이 계산해줍니다.
   블록을 채워주면 block 수가 작아지고, 블록을 빼주면 block 수가 커지겠습니다.
4. 집터를 모두 순회한 이후에 block 수가 0 이상이고,
   height에서의 소요시간보다 현재 땅 높이에서의 소요시간이 짧거나 같으면
   height값은 현재 땅 높이로 업데이트해줍니다.

주의할 점! 먼저 block이 0보다 작아졌을 때 바로 break를 하면 안됩니다.
나머지 집터를 순회하는 과정에서 인벤토리에 블록이 들어올 수도 있기 때문입니다.
따라서 모든 집터를 다 순회한 후에 block값을 체크해주어야 합니다.

다음은 time[g] <= time[height] 코드 부분입니다.
왜 <가 아닌 <= 일까요?
문제에는 "답이 여러 개 있을 때 그중에서 땅의 높이가 가장 높은 것을 출력하시오" 라는 부분이 있습니다.
g는 1부터 오름차순으로 커지므로 g는 당연히 height보다 크겠죠?
따라서 time[g] == time[height]인 경우도 height를 g로 업데이트해주어야 합니다.

import sys

N, M, B = map(int, sys.stdin.readline().split())
ground = []
for _ in range(N):
    ground.extend(map(int, sys.stdin.readline().split()))

time = [0 for i in range(257)] # time[k]에 땅높이가 k일때의 소요시간 저장
height = 0
for g in range(257):
    block = B # 인벤토리에 남은 블록 수
    for i in ground:
        if i <= g: # i == g이면 g-i=0
            time[g] += g - i
            block -= g - i
        else:
            time[g] += 2 * (i - g)
            block += i - g
    if block >= 0 and time[g] <= time[height]: # 오름차순으로 순회하므로, 답이 여러 개 있을 때 그중에서 땅의 높이가 가장 높은 것을 저장하게 됨
        height = g # 최소 소요 시간인 땅높이 저장

print(time[height], height)

height에 최소 소요 시간을 가지는 땅 높이를 저장하며 코드가 진행되는데요,
수행 과정에서 최소값 또는 최대값을 가진 데이터를 선택하는 그리디 알고리즘으로 볼 수 있습니다.