백준 18111 마인크래프트

문제

마인크래프트

땅을 고르게 하는 최소 시간 계산

난이도 : Silver2

---

풀이

1. 가능한 땅의 높이 최소부터 최대까지 모두 계산
2. 땅을 깎고 쌓는 경우를 모두 계산해 최솟값만 출력

---

코드

import sys

N, M, B = list(map(int, sys.stdin.readline().split()))
heights = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
heights = [i for h in heights for i in h]  # 2차원 배열 1차원으로 flatten

low, high = min(heights), max(heights)
answers = []

for opt in range(low, high+1):  # 높이의 최소, 최대 사이 값들을 모두 탐색
    block = B
    times = 0  # 전체 시간
    for h in heights:  # 블럭 높이를 opt로 모두 깎거나 쌓음
        if h > opt:  # 블럭이 opt보다 크면,
            block += (h-opt)  # 인벤토리에 차이만큼 저장하고
            times += 2 * (h-opt)  # 2초가 걸리므로 시간에 2*차이 스택

        elif h < opt:  # 그 반대
            block -= (opt-h)
            times += (opt-h)
        
    if block >= 0:  # 남은 블럭 개수가 0 이상인 것만 저장
        answers.append((times, opt))
    else:  # 남은 블럭이 0보다 작아지면, 그 이후 케이스들도 모두 0보다 작으므로 탈출
        break
    
answers = sorted(answers, key=lambda x: (x[0], -x[1]))  # 시간은 오름차순, 높이는 내림차순 정렬
print(answers[0][0], answers[0][1])

---

결과

pypy3으로는 통과했지만, python3는 시간 초과가 나는 코드다.
더 시간 복잡도를 줄일 수 있는 알고리즘으로 변경해야 한다.