[백준] 18111번 파이썬 (마인크래프트)

1. 문제와 예제

문제

예제

---

2. 전체 코드

import sys
input = sys.stdin.readline

# 입력 받기
N, M, B = map(int, input().split()) # 집터의 세로 길이, 가로 길이, 인벤토리에 있는 블록의 개수
h_dct = {h : 0 for h in range(257)} # 현재 땅의 높이 각각의 개수

# {'땅의 높이': '개수}를 dict 형태로
for _ in range(N):
    temp = list(map(int, input().split()))
    for h in temp:
        h_dct[h] += 1

h_dct = list(h_dct.items()) # for문에 사용하기 위해 타입 변경
time_lst = [] # 걸리는 시간 리스트

for i in range(257):
    over = [(k, v) for k, v in h_dct if k > i and v != 0] # 현재 높이(k)가 원하는 높이(i)보다 높은 경우
    under = [(k, v) for k, v in h_dct if k < i and v != 0] # 낮은 경우
    time = 0 # 걸리는 시간
    block = B # 남은 인벤토리 블록 개수

    for h, cnt in over:
        time += 2 * (h - i) * cnt
        block += (h - i) * cnt
    for h, cnt in under:
        time += (i - h) * cnt
        block -= (i - h) * cnt

    if block < 0: # 원하는 높이(i)를 구현할 수 없는 경우
        break # time_lst에 추가하지 않음
    time_lst.append(time) # break를 거치지 않은 경우 추가

min_time = min(time_lst) # 걸리는 시간 중 최솟값
idx_lst = [idx for idx, t in enumerate(time_lst) if t == min_time] # 최소 걸리는 시간의 인덱스들 리스트
max_idx = max(idx_lst) # 인덱스들 중 최댓값

# 결과 출력하기
print(min_time, max_idx)

---

3. 코드 해설

모든 경우의 수에 대해 해봐야 하는 브루트포스 알고리즘 문제다.

추가 설명이 필요한 부분은 'idx_lst ~ max(idx_lst)' 이 두 줄일 것 같다. 원하는 높이(i)를 구현할 수 없는 경우에는 time_lst에 추가하지 않았는데 어떻게 인덱스로 땅의 높이를 구해낼 수 있는 것인지에 대한 부분. 결국 'block < 0'인 경우는 인벤토리에 갖고 있던 블록의 개수가 모자랐다는 뜻이고 이는 높이가 높은 쪽에 속한다. 따라서 원하는 높이(i)를 0부터 올려나갈 때 어떤 높이까지 time_lst에 추가되다가 그 다음 높이부터 256까지는 모든 i에 대해 'block < 0'이 발생해 time_lst에 추가되지 않는다. 따라서 time_lst에 추가된 경우에 한해서는 인덱스가 곧 땅의 높이를 나타낸다.