[백준 18111] 마인크래프트 - 브루트포스

접근

• 만들어야 하는 높이는 각 좌표의 높이의 사이에 있는 높이일 것이다 (최소높이 ~ 최고높이)
• 각 높이를 만들 때, 채워야하는 좌표가 있고 깍아야하는 좌표가 있다.
• 깍으면 블록 개수가 늘어나므로, 이를 잘 고려하여 각 높이를 만들 때 필요한 시간을 계산한다.
• 필요한 시간이 같은 높이가 여러개라면, 한번에 깍을 수 있다

 

코드

from collections import Counter

def solution(arr, b):
    # 쌓여있는 블록들의 최소 높이부터 최대 높이 까지의 범위를 저장
    heights = [ i for i in range(min(arr), max(arr)+1)]

    # 높이가 같은 블록의 개수를 Counter를 사용해 저장
    cd = Counter(arr)

    # 걸리는 시간과 높이 저장
    time_height = []

    for height in heights:
        # 깍아야 하는 블록 수
        down_cnt = 0
        # 쌓아야 하는 블록 수
        up_cnt = 0
        for key, value in cd.items():
            # 현재 블록의 높이가 목표로 하는 높이보다 낮으면 음수이므로, up_cnt 에 더함
            if key - height < 0:
                up_cnt += abs(key - height) * value
            else:
                down_cnt += abs(key - height) * value
        #print(height, down_cnt, up_cnt)
        # 깍은 블록 수(down_cnt) 보다 쌓아야 하는 블록 수(up_cnt + b)가 많으면 쌓을 수 있는 높이가 아니므로 그냥 패스
        if down_cnt+b < up_cnt:
            pass
        # 깍거나 쌓는 블록에 걸리는 시간과 높이를 저장
        else:
            time_height.append([down_cnt*2 + up_cnt, height])
    
    time_height.sort(key=lambda x: (x[0], -x[1]))
    print(time_height[0][0], time_height[0][1])
    #print(time_height)

n, m, b = map(int, input().split())

arr = []
for _ in range(n):
    arr += list(map(int, input().split()))

#print(arr)
solution(arr, b)