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

처음엔 어떻게 풀어야 할지 조금 고민했다. 경계값을 따져보면 땅을 최대할 팔 수 있는 만큼 파서 평탄화 하는 방법과(높이를 최소로), 사용 가능한 블록을 최대한 써서 평탄화 하는 방법(높이를 최대로)일 것이다. 그 사이에서 시간을 최소로 하는 방법을 찾아야 한다.

import sys, math

N, M, B = map(int, input().split())
arr = []
total = B

for _ in range(N): # 다루기 쉬운 1차원 배열로 받음
    i = list(map(int, sys.stdin.readline().split()))
    arr += i
    total += sum(i)

min_height = min(arr)
max_height = math.floor(total / (N * M))
result_time = 1e9
result_height = 0

# 최종적으로 inven >= 0이 보장됨.
for height in range(min_height, max_height + 1):
    time = 0
    for i in arr:
        if i > height:
            time += (i - height) * 2
        elif i < height:
            time += height - i
        if time > result_time:
            break
    if time < result_time:
        result_time = time
        result_height = height
    elif time == result_time and height > result_height:
        result_height = height

print("%d %d" % (result_time, result_height))

처음에 시간 초과가 떠서 다른 방법으로 여러 번 시도해 보았으나 결과는 동일했다. 언어를 Python 3에서 pypy로 바꾸어 제출하니 바로 통과되었다.
다음엔 pypy로 먼저 제출해 봐야겠다.

---

11.24 추가)

백준 11723번: 집합 문제를 풀 때 같은 코드를 pypy로 제출하면 메모리 초과가 뜨고, Python 3으로 제출하면 통과된다.

Python3 와 PyPy3 차이

위 글에 두 언어의 차이점이 잘 설명되어 있었다.
PyPy3은 메모리를 사용하여 자주 쓰이는 코드를 캐싱하는 기능이 있다. 이것이 메모리에 특이점을 둔 문제를 풀 때 단점으로 작용할 수 있음을 알게 되었다.