[백준] #18111 마인크래프트 (python)

https://www.acmicpc.net/problem/18111

문제풀이

import sys
input=sys.stdin.readline

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

max=sys.maxsize
floor=0

for _ in range(0,N):
    
    k=list(map(int,input().split()))
    height.append(k)
    
for k in range(0,257):
    lack=0
    enough=0

    for i in range(0,N):

        for j in range(0,M):
            if height[i][j]>k:
                enough+=height[i][j]-k
            else:
                lack+=k-height[i][j]
            
    if enough+B>=lack:
        if 2*enough+lack <= max:
            
            max=2*enough+lack
            floor=k
        
print(max,floor)

정리

출력 부분에 답이 여러 개 있다면 그중에서 땅의 높이가 가장 높은 것을 출력하라고 하였으므로 땅의 높이가 0부터 256일 때까지 모두 구한 후 그 중에서 조건에 맞는 값을 출력한다.

 

(i,j) 영역의 땅 높이가 기준이 되는 k 높이보다 작을 경우에는 블록을 놓아줘야 하고 k높이보다 높을 경우에는 블록을 인벤토리에 수거해 줘야 한다.  모든 좌표에 대해서 부족한 블록의 수와 충분한 블록의 수를 구해준다. 

인벤토리에 수거한 블록의 수 + 원래 가지고 있던 블록 수가 부족한 블록수보다 크거나 같은 경우에 대해서만 모든 좌표를 같은 높이로 할 수 있기 때문에 조건을 작성한다. 

총 소모되는 시간은 2*회수한 블록수 + 설치한 블록수이다. 총 소모되는 시간이 최소인 경우를 구해야 하므로 sys.maxsize를 이용한다.

max보다 작거나 같은 경우에만 max 값이 재할당되도록 코드를 작성해준다. 시간이 같다면 땅의 높이가 최대여야 하기 때문.

 

그때의 소모된 시간과 k값(땅의 높이)를 출력한다.