[CLASS 2]백준 18111번 - 마인크래프트

18111번 : 마인크래프트

 

이 문제를 보고 한참 고민했다. 뭔가 엄청난 알고리즘을 사용해야 하나?(알고 있는 것도 없지만) 라고 생각하던 와중 M,N 의 범위가 1부터 500이고, 높이의 범위는 0~256인것을 알고 그냥 브루트포스를 사용하면 되겠다고 판단하여 코드를 작성하였다.

 

일단 받은 높이들 중 최대높이 이하 최소높이 이상의 높이에서만 검사해보면 된다. 그 이외의 높이들은 쓸데없이 블럭을 캐거나 놓아야한다.

 

내 코드(시간 초과):

n,m,b = map(int,input().split())
ground = [list(map(int,input().split())) for y in range(n)]
maxHeight = max(max(ground))
minHeight = min(min(ground))
times = []
for height in range(maxHeight,minHeight-1,-1):
    inv = b
    time = 0
    for y in ground:
        for x in y:
            need = height - x
            inv -= need
            if need > 0:
                time += need
            elif need < 0:
                time += need * -2
    
    if inv >= 0:
        times.append((time,height))

times = sorted(times,key=lambda time:time[0])
print(times[0][0], times[0][1])

 

처음에 짠 코드는 그냥 다 검사해보는 것이었다. 2중배열을 하나 만들어서 말그대로 모든 좌표의 모든 높이를 다 검사해서 최대높이 이하 최소높이 이상의 높이에 대해 고르게 만드려면 얼마나의 시간이 걸리는지 다 검사했었다. 이렇게 작성하니 시간 초과 당했다. 같은 코드를 pypy3으로 제출하니 정답 판정을 받았지만 같은 높이에 대해 계속 빼는 연산을 해야 하는것에 비효율적임을 느끼고 collections의 Counter를 사용해서 다시 작성하였다.

 

내 코드(Counter사용):

import sys
from collections import Counter

input = sys.stdin.readline
n,m,b = map(int,input().split())
heights = []
for _ in range(n):
    heights += list(map(int,input().split()))
# 모든 블럭 개수 저장
allBlocks = sum(heights)

#Counter변수로 변환
heights = Counter(heights)

# 큰 값 먼저 대입
bestTime = 256 * 500 * 500 * 3
bestHeight = 256

for height in range(max(heights),min(heights)-1,-1):
    time = 0
    # need변수는 필요한 블럭의 개수. + 라면 해당 높이로 고르게 하기 불가능
    need = (height * n * m) - (allBlocks + b)
    if need <= 0:
        for h,c in heights.items():
        	# 목표 높이보다 해당 좌표 높이가 높다면 캐기
            if h > height:
                time += (h - height) * 2 * c
            	# 목표 높이보다 해당 좌표 높이가 낮다면 놓기
            elif h < height:
                time += (h - height) * -c
        if time < bestTime:
            bestHeight = height
            bestTime = time

print(bestTime,bestHeight)

 

이렇게 작성하고 나니 시간이 비약적으로 상승하였다. 이 풀이의 핵심은 need 변수와 Counter인데, need 변수는 먼저 해당 높이의 직육면체를 만들기 위해 총 몇개의 블럭이 필요한지 계산한 후 현재 있는 모든 블럭의 개수에서 인벤토리의 블럭의 개수를 뺀 값이다. 이 값이 + 라면 인벤토리의 모든 블럭을 쓰고 높은 블럭들을 깎더라도 해당 높이를 만들 수 없으므로 해당 높이를 넘긴다. 0이하라면 만들 수 있는 경우이고 이 높이에 대해 시간을 계산한 다음 bestTime 과 비교하여 저장한다. 시간을 계산할 때 Counter를 사용해서 같은 높이는 다시 검사할 일 없이 c를 곱하여 처리하기 때문에 시간 향상이 있었다. 높이는 for문이 최대높이에서부터 거꾸로 검사하기 때문에 시간이 줄어들었다면 따로 검사할 필요 없다.

 

CLASS 2 완료!