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

문제

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

문제에서 주어진 규칙에 따라 땅을 고르게 만드는 데 필요한 시간의 최솟값과 그때의 층수를 출력하는 문제이다.

 

접근

처음에는 이분 탐색을 활용해 코드를 작성했으나 문제를 풀 수 없었다. 찾아야 하는 것은 시간의 최솟값인데 층수를 기준으로 이분 탐색을 진행하고 있었기 때문이다.

브루트포스를 활용해 코드를 다시 작성했다. 층수 범위가 0층~256층이므로, Counter를 활용해 n층인 블록 개수를 따로 저장해 사용했다.

 

코드

import sys
from collections import Counter
input = sys.stdin.readline

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

for _ in range(N):
    grounds += list(map(int, input().split()))

floors = Counter(grounds)
l = min(grounds)
h = max(grounds)
time = float('inf')
ans = -1

for i in range(l, h+1):
    up, down = 0, 0
    for f, n in floors.items():
        if f > i:
            up += (f - i) * n
        elif f < i:
            down += (i - f) * n
    tmp = 2*up + down
    if down <= up + B and tmp <= time:
        time = tmp
        ans = i
        
print(time, ans)