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

18111번: 마인크래프트 (acmicpc.net)

18111번: 마인크래프트

• 땅의 높이를 모두 동일하게 만드는 ‘땅 고르기’ 작업
• 세로N, 가로M 크기의 집터, 맨 왼쪽 위의 좌표 (0, 0)

 

• 좌표 (i, j)의 가장 위에 있는 블록 → 인벤토리 : 1초
• 인벤토리 → 좌표 (i, j)의 가장 위에 있는 블록 위에 놓음 : 2초
• 0 ≤ 땅의 높이 ≤ 256

땅을 고르는 데 걸리는 최소시간의 (시간, 높이) 출력 (높이가 가장 높은 답)

💡 알고리즘

구현, 브루트포스 알고리즘

💡 접근

처음에는 가장 많이 나오는 수를 기준으로 더 높은 블럭/ 낮은 블럭을 센다 → 가장 높은 높이부터 되는지 안되는지 check

이 방법으로 코드를 작성하였으나.. 땅의 높이가 제한적이기 때문에 굳이 가장 많이 나타나는 높이를 기준으로 생각할 필요가 없었다.

→ (0 ~ 256) 모든 높이에 대하여 가능한지 check

💡 코드

import sys

N, M, B = map(int, sys.stdin.readline().split())

arr = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]

height = 0
minn = 1000000000000000000000000000000
for i in range (257) :
    up = 0
    down = 0
    for j in range (N) :
        for k in range (M) :
            if arr[j][k] < i :
                up += i -arr[j][k]   # 블럭을 올리는 경우
            else :
                down += arr[j][k] - i    # 블럭을 치우는 경우
    inven = down + B
    if inven < up :
        continue
    time = down * 2 + up
    if time <= minn :
        minn = time
        height = i
print(minn, height)

• 불필요한 계산을 줄이기 위한 inven < up if문 작성