[#18111] 마인크래프트

❓ Question

📖 Before Start

백준을 시작한 지 얼마 되지 않은 나로서는 아직까지 이런 긴 문항을 가진 문제가 참 익숙치 않다.

하지만 그렇다고 해서 마냥 포기할 수는 없는 노릇이다. 언제까지고 실버 5~4 문제만 풀 수는 없으니까.
그래서 이 참에 눈 딱 감고 한번 도전해봤다. 틀리더라도 해답을 보면서 스스로 공부를 하면 될 것이다...

✒️ Design Algorithm

이 문제를 보면서 느낀 점은 딱 하나였다. 이거.. 전부 순회하면서 경우의 수를 찾아야 겠는데?

안타깝게도 브루트 포스라는 알고리즘을 나는 백준 문제를 풀면서 처음 접하였다. 모든 경우의 수를 완전 탐색하여 문제를 100% 해결하는 방식이라고 하는데, 정말 쉽게 말하자면 그냥 단순 노가다 인 것 같다..
아래는 필자가 문제를 풀기 전 작성한 알고리즘 설계이다.

땅의 높이는 0부터 256 이며, 메꿔야 할 지역의 너비는 n x m 사이즈이다.
n, m, b를 첫번째 줄에 입력 받으며, b 는 현재 유저가 보유한 블럭의 수다.

• 땅 파기 : 해당 위치의 블록을 1칸 제거하며, 높이가 1 감소한다.
• 블럭 설치 : 보유한 블록을 사용하여, 해당 위치의 높이를 1 증가시킨다.
• 땅 파기의 경우 2초가, 블럭 설치의 경우 한 블럭 당 1초가 소요된다.

1. 먼저 n x m 구역의 블록 높이를 조회한 후, 최소 높이와 최대 높이를 구한다.

2. 최소 높이와 최대 높이 간의 간격을 한 칸 씩 조회하며, 하단의 시뮬레이션을 돌린다.

   • 현재 높이에서 설치해야 하는 블록의 갯수와 파괴해야 하는 블록의 갯수를 계산
   • (보유한 블록) + (파괴한 블록) >= (설치해야 하는 블록) 조건 판별
   • 조건이 True라면, 평지화 작업까지 걸리는 시간을 산술하여 적용시킴.

💻 Making Own Code

import sys
from math import inf

n, m, b = map(int, sys.stdin.readline().split())
region, result = [], []
for i in range(n):
    region.append(list(map(int, sys.stdin.readline().split())))

min_h, max_h = min(map(min, region)), max(map(max, region))
least_time, best_height = inf, 256

def check_time(h):
    need_block, has_block = 0, 0
    for j in range(n):
        for k in range(m):
            current_h = region[j][k]
            if current_h == h:
                continue
            elif current_h > h:
                has_block += current_h - h
            elif current_h < h:
                need_block += h - current_h
    if need_block <= has_block + b:
        return has_block * 2 + need_block
    else:
        return None

for h in range(min_h, max_h+1):
    time = check_time(h)
    if time is not None:
        if time <= least_time:
            least_time, best_height = time, h
print(least_time, best_height)

결국 브루트 포스 관련 문제는 얼마나 내가 구현을 잘 하느냐의 싸움인 것 같다.

Math 라이브러리의 inf 를 사용하여 탐색의 기준이 되는 최소 시간 변수의 값을 무한대로 설정하였다.
높이를 0부터 256까지 탐색하는 방법도 있지만, 최대한 실행을 줄이고자 최소, 최대 높이를 먼저 구했다.
그런 후, 반복문을 통해 각 높이 별로 소요되는 시간을 계산하여 현재 저장된 최소 시간과 대조하였다.

이번 마인크래프트 문제도 제법 머리를 싸맸지만, 정답을 맞추고 나니 마음이 홀가분하다.

처음에는 Python 3로 답을 제출했으나, 어김없이 시간 초과가 뜨는 바람에 PyPy3 으로 다시 제출하였다.
코드를 최대한 짧게 쓴다고 노력을 하였으나 아직 갈 길이 멀어 보인다. 더 깔끔한 방법을 찾아보자!