BOJ 18111 - 마인크래프트

문제

백준 온라인 저지 - 18111번

풀이 과정

격자 형태의 땅이 주어지고 높이를 맞추기 위한 최소 시간과 그때의 높이를 구하는 문제입니다.

처음에는 이분 탐색 을 이용해서 최소 시간을 구하려고 했지만 동일한 시간에 높이가 최대인 경우를 찾는 과정이
명확하지 않아서 그냥 완전 탐색 으로 해결하는 것으로 방향을 잡았습니다.

총 0 ~ 256 의 높이를 탐색하면 되는데 이때 격자를 O(N^2) 으로 탐색하면 시간 초과가 발생합니다.
대신 전처리 과정을 통해 각 격자의 높이 값을 저장하고 기준 높이보다 작거나 큰 개수를 세어 필요한 시간 값을 계산하면 됩니다.

코드

import sys

N, M, B = list(map(int, sys.stdin.readline().split()))
board = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]


def pre_processing():
    heights = {}

    for x in range(N):
        for y in range(M):
            height = board[x][y]

            if height in heights:
                heights[height] += 1
            else:
                heights[height] = 1

    return heights


def calc_groundwork(dist, height):
    remove, addon = 0, 0

    for h, cnt in dist.items():
        if h > height:
            remove += (h - height) * cnt
        elif h < height:
            addon += (height - h) * cnt

    inventory = B + remove

    if inventory < addon:
        return sys.maxsize
    else:
        time = remove * 2 + addon
        return time


def solution():
    dist = pre_processing()
    ans_time, ans_height = sys.maxsize, 0

    for height in range(257):
        time = calc_groundwork(dist, height)

        if time <= ans_time:
            ans_time = time
            ans_height = height

    print(f"{ans_time} {ans_height}")


solution()