[Python 3] BOJ - 18111 "마인크래프트"

 # 문제 링크 : https://www.acmicpc.net/problem/18111

18111번: 마인크래프트

 # 풀이 : 

Python, PyPy 모두 추가시간이 주어지지 않으므로 도중에 검사하기보다 모든 원소를 돌고나서 체크를 하는것이 낫다. 문제의 조건에서 연산은 두 가지이다.

1) 현재의 높이가 목표 높이보다 낮다면, 인벤토리에서 블록을 꺼내 현재 높이에 붙인다

    - 결과 : 현재 높이 1증가, 인벤토리 1 감소

2) 현재의 높이가 목표 높이보다 높다면, 현재 높이의 가장 위의 블록을 인벤토리로 넣는다

    - 결과 : 현재 높이 1감소, 인벤토리 1 증가

개인적으로 문제의 핵심은 인벤토리로 들어가는 블록의 갯수와 초기 인벤토리를 합한 것이 인벤토리에서 나가는 블록의 갯수보다 크거나 같다면 그 목표높이로 땅을 고를 수 있다는 것이다.

추가적으로 코드에서는 3중 for문을 돌지만 실제로는 최대 높이가 257개(0 포함), 행렬의 최대 사이즈는 250,000이므로 256 * 250,000 = 64,250,000 이므로 충분히 1초만에 모든 경우를 계산할 수 있다.

 

# 코드

import sys
n, m, b = map(int, sys.stdin.readline().split())
table = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
height = 0
ans = 1000000000000000000000000000000
for i in range(257):
    max = 0
    min = 0
    for j in range(n):
        for k in range(m):
            if table[j][k] < i:
                min += (i - table[j][k])
            else:
                max += (table[j][k] - i)
    inventory = max + b
    if inventory < min:
        continue
    time = 2 * max + min
    if time <= ans:
    # 시간이 같을 때는 높이가 높은 순으로 출력하라는 조건에 맞게
    # for i in range(257)은 항상 i가 오름차순으로 돌기 때문에
    # 시간이 같아도 최종적으로는 높이가 높은 순으로 나오게 된다
        ans = time
        height = i
print(ans, height)