백준 18111번 마인크래프트 [Python]

문제 출처: https://www.acmicpc.net/problem/18111

18111번: 마인크래프트

 

 

Sol)

import sys
input = sys.stdin.readline


row, col, inventory = map(int, input().split())
blocks = []
for i in range(row):
    blocks += list(map(int, input().split()))

min_time = 500*500*2*257
ans_height = blocks[0]
blocks_out = sum(blocks)
for target_h in range(max(blocks), min(blocks) - 1, -1):
    if blocks_out + inventory >= target_h * row * col:
        time = 0
        for b in blocks:
            diff = b - target_h
            if diff > 0:
                time += diff * 2
            elif diff < 0:
                time -= diff * 1

        if time < min_time:
            min_time = time
            ans_height = target_h

print(min_time, ans_height)

 

• 풀이 방향

일단 필요한 작업들을 쪼개봤다.

1. 땅고르기의 기준이 될 블럭 높이를 기준으로 정한다.

2. 기준 블럭보다 높으면 깎는다.

3. 기준 블럭보다 낮은면 쌓는다.

4. 인벤토리에 있는 블럭들로 기준 높이를 맞출 수 있는지 확인한다.

5. 같은 시간이라면 가장 높은 기준높이로 답을 유지한다.

 

• 풀이

1번 작업은 for문을 돌면서 기준 높이를 하나씩 검사하면 될 것 같다. 범위는 최대 0 ~ 256 이다. 하지만 0 ~ 256을 다 검사하는 것 보다는 필드에 나와있는 블럭의 min값과 max값 사이의 높이만 검사하는 것이 더 효율적이다. 또한 5번 작업을 위해 max 값부터 검사를 하고 if문에 등호를 넣지 않아 더 낮은 높이라면 시간이 더 짧을 때만 min_time이 갱신되도록 했다.

 

1번 작업 for문 안에 2번 작업과 3번 작업을 해야하는데 각각 for문을 2번 쓰면 block 수가 최대 500*500이 될 수 있으므로 O(500*500*256 + 500*500*256) 이 된다. 이는 O(1억)이 넘어가 1초를 넘어가게 된다. 따라서 2번 작업과 3번 작업은 하나의 for문으로 처리한다. 

 

4번 작업의 경우 inventory 변수를 직접 건드리면 다른 케이스들에 영향을 미치고, inventory 값을 복사한 다른 변수를 새로 만들자니 코드가 깔끔하지 않았다. 이를 해결하기 위해 (이미 필드에 나와있는 블럭의 수 + 인벤토리에 있는 블럭의 수)로 주어진 좌표들을 기준높이로 모두 채울 수 있는지 검사하는 if문을 만들어 반복 횟수도 줄이고 코드도 간결하게 만들 수 있었다.

 

• 문제에 대한 사견

오랜만에 문제를 풀었더니 PS초반에 했던 실수들이 똑같이 나왔다. local로 선언해야 하는 변수를 global로 선언한다든가, 숫자의 범위를 잘못 고려한다든가 하는 행동들로 인해 계속 틀렸습니다를 받았다. 전체적인 로직도 중요하지만 작은 부분의 디테일을 더욱 신경써야함을 다시한번 느꼈다.