[백준/18111/파이썬] 마인크래프트

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

18111번: 마인크래프트

Problem

• 목재를 충분히 모은 lvalue는 집을 짓기로 하였다. 하지만 고르지 않은 땅에는 집을 지을 수 없기 때문에 땅의 높이를 모두 동일하게 만드는 ‘땅 고르기’ 작업을 해야 한다.
• ‘땅 고르기’ 작업에 걸리는 최소 시간과 그 경우 땅의 높이를 출력하시오.

조건

땅고르기 작업

• lvalue는 세로 N, 가로 M 크기의 집터를 골랐다. 집터 맨 왼쪽 위의 좌표는 (0, 0)이다. 우리의 목적은 이 집터 내의 땅의 높이를 일정하게 바꾸는 것이다. 우리는 다음과 같은 두 종류의 작업을 할 수 있다.

1. 좌표 (i, j)의 가장 위에 있는 블록을 제거하여 인벤토리에 넣는다.
2. 인벤토리에서 블록 하나를 꺼내어 좌표 (i, j)의 가장 위에 있는 블록 위에 놓는다.

• 1번 작업은 2초가 걸리며, 2번 작업은 1초가 걸린다. 밤에는 무서운 몬스터들이 나오기 때문에 최대한 빨리 땅 고르기 작업을 마쳐야 한다.
• 단, 집터 아래에 동굴 등 빈 공간은 존재하지 않으며, 집터 바깥에서 블록을 가져올 수 없다. 또한, 작업을 시작할 때 인벤토리에는 B개의 블록이 들어 있다. 땅의 높이는 256블록을 초과할 수 없으며, 음수가 될 수 없다.

SOL

처음에는 단순히 같지않으면 높이만 맞춰주면 되는 문제 같았지만, 가진 블록의 수의 제한도 있고, 블록의 상황에 따라서, 시간이 더 걸리는 1번 작업을 하는게 이득일 수도, 직관적으로 시간이 덜 걸리는 2번 작업을 하는게 이득일 수도 있게 된다.

 

완전탐색

높이는 최대 256 이고, N,M은 500*500이다. 즉, 256*500*500인 3중반복을 한다면, 64,000,000으로 충분히 1초안에 해결이 가능하다.

즉, 목표 높이가 0~256인 모든 경우를 탐색하는 식으로 구현을 할거다. 

예를들어, 목표높이가 2인 경우, 현재 땅의 높이가 0이라면, 2개를 더 쌓아야 한다. 목표높이가 0인 경우, 땅의 높이가 1이라면, 블럭을 캐서 인벤토리에 넣어야 한다.

 

import sys
input= sys.stdin.readline

N,M,B= map(int,input().split())
land=[list(map(int,input().split())) for _ in range(N)]
ans=sys.maxsize
height=0

for i in range(257):
    stack_block=0
    pop_block=0
    for j in range(N):
        for k in range(M):
            #input의 높이가 , 목표 높이보다 작다면, 인벤토리에서 블럭을 꺼내서 쌓아야한다.
            if land[j][k] < i:
                stack_block +=(i-land[j][k])
            else:
            #input의 높이가, 목표 높이보다 크거나 같다면 , 캐서 인벤토리에 넣어야한다.
                pop_block +=(land[j][k]-i)
    have_block=B+pop_block
    # 가진 블록보다, 필요한 블럭이 많다면 불가능한 경우다. 넘어간다
    if have_block<stack_block:
        continue
    time= 2*pop_block + stack_block
    if time<=ans:
        ans=time
        height=i

print(ans,height)