[Python 3] BOJ - 18111 "마인크래프트"
# 문제 링크 : https://www.acmicpc.net/problem/18111
18111번: 마인크래프트
팀 레드시프트는 대회 준비를 하다가 지루해져서 샌드박스 게임인 ‘마인크래프트’를 켰다. 마인크래프트는 1 × 1 × 1(세로, 가로, 높이) 크기의 블록들로 이루어진 3차원 세계에서 자유롭게 땅을 파거나 집을 지을 수 있는 게임이다. 목재를 충분히 모은 lvalue는 집을 짓기로 하였다. 하지만 고르지 않은 땅에는 집을 지을 수 없기 때문에 땅의 높이를 모두 동일하게 만드는 ‘땅 고르기’ 작업을 해야 한다. lvalue는 세로 N, 가로 M 크기의 집터를
www.acmicpc.net
# 풀이 :
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)