[Brute Force] 백준 18111 마인크래프트 - Python

 

[ Contents ]

 

 

1. 문제 (링크 참조)

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

18111번: 마인크래프트

 

 

2. 문제 풀이

1) 블록 제거: 2초, 블록 +1
2) 블록 추가: 1초, 블록 - 1

 주어진 블록의 개수로 최대한 빠르게 평평하게 만드는 문제입니다. 동일한 시간이 걸릴 경우, 더 높은 경우를 출력해야 합니다. 

 

2022.01.16 - [Algorithm] - [Algorithm] 브루트 포스(Brute Force)는 노가다 기법?

[Algorithm] 브루트 포스(Brute Force)는 노가다 기법?

 마인크래프트를 해본 사람이라면 쉽게 이해가 가는 문제입니다. 실제 게임에서도 블록 쌓기보다는 블록 제거가 오래 걸리죠.

 이 문제는 '브루트포스' 문제로, 블록의 최소 높이에서 최대 높이까지 1씩 올려가며 확인해야 합니다. 다만 언어별 추가시간이 없어서, 파이썬보다는 pypy3로 실행해야 통과할 가능성이 높습니다.

 

 

 

3. 코드

from collections import Counter
N, M, B = map(int, input().split())
block = []
for i in range(N):
    block.extend(map(int, input().split()))

mode = Counter(block).most_common()[0][0] #최빈값
block.sort(reverse=True) #내림차순으로 정렬

def mineCraft(mode):
    inventory = B #인벤토리 블록 수
    time = 0 #필요한 시간
    for i in block:
        if i > mode: #최빈값보다 큼
            time += 2*(i-mode)
            inventory += i-mode

        elif i < mode: #최빈값보다 작음
            time += mode-i
            inventory -= mode-i

    # 블록이 부족할 경우, 최빈값 -1하고 다시 반복
    if inventory < 0:
        return mineCraft(mode-1)
    else:
        return time, mode

t1, h1 = mineCraft(mode)
t2, h2 = mineCraft(mode+1)

if t1 == t2:
    print(t2, h2)
else:
    print(t1, h1)

 처음에는 최빈값으로 높이를 맞춰서 풀려고 했습니다. 해봤자, 높이 하나쯤 더 쌓을 수 있겠지 싶어서 구현했으나 실패했습니다. 예를 들어 높이가 100 99 0 0 일 때, 최빈값은 0이지만 블록의 갯수가 충분하다면 99를 맞추는 게 더 빠르고 높은 높이입니다. (블록을 쌓는 시간 1초 / 블록을 부수는 시간 2초)

 

 

N, M, B = map(int, input().split())
block = []
for i in range(N):
    block.extend(map(int, input().split()))

res = [] # 결과값을 저장할 리스트
#가장 낮은 높이부터 가장 높은 높이까지 탐색
for h in range(min(block), max(block)+1):
    inventory = B #인벤토리 블록 수
    time = 0 #필요한 시간
    for i in block:
        if i > h: #지정 높이보다 큼
            time += 2*(i-h)
            inventory += i-h

        elif i < h: #지정 높이보다 작음
            time += h-i
            inventory -= h-i

    # 블록이 부족할 경우, 더 이상 높힐 수 없음
    if inventory < 0:
        break
    else:
        res.append([time, h])

res.sort(key=lambda x: (x[0], -x[1])) #시간은 작을수록, 높이는 높을수록 좋음
print(res[0][0], res[0][1])

 브루트포스 기법으로, 가장 낮은 높이부터 1씩 올려갑니다. 블록이 부족한 경우에는 더 이상 높일 수 없다는 뜻이므로 반복문을 빠져나옵니다.

 결과값들을 낮은 시간, 높은 높이순으로 정렬하고 가장 첫 번째 항목을 출력합니다.

 저는 블록마다 필요한 시간을 계산했지만, 동일한 높이의 블록을 묶어서 계산하면 좀 더 시간을 아낄 수 있습니다.