18111번: 마인크래프트

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

Explanation:

1 x 1 x 1(세로,가로,높이) 크기의 블록들로 이루어진 3차원 세계에서 땅을 평평하게 만들어야 한다. 집터 맨 왼쪽 위의 좌표 (0,0)을 기준으로 땅의 높이를 일정하게 바꾸어야 하는데, 다음과 같은 조건이 있다.

1. 좌표 (i, j)의 가장 위에 있는 블록을 제거하여 인벤토리에 넣는다.
2. 인벤토리에서 블록 하나를 꺼내어 좌표 (i, j)의 가장 위에 있는 블록 위에 놓는다.

1번 작업은 2초 소요, 2번 작업은 1초 소요된다. '땅 고르기' 작업에 걸리는 최소 시간과 그 경우의 땅 높이를 출력하는데, 답이 여러 개 존재한다면 그 중에서 땅의 높이가 가장 높은 것을 출력한다.

Algorithm:

brute force

땅의 높이는 256블록을 초과하지 않으므로, brute force로 해결이 가능하다. 모든 땅의 높이를 모두 탐색하면서

1. 비교 대상인 땅의 높이가 주어진 땅의 높이보다 큰 경우
   if i > block[x][y] :
use_block += i - block[x][y]
   비교 대상인 땅의 높이에서 주어진 땅의 높이를 빼고 use_block에 저장해준다. 그리고 땅이 높기 때문에 블록을 채워넣어야 한다.(블록을 채우는 작업은 2번에 해당하고 1초가 걸림)

2. 주어진 땅의 높이가 비교 대상인 땅의 높이보다 큰 경우
   if block[x][y] > i :
take_block = block[x][y] - i
   1번 작업에 해당하며 2초가 걸린다.

1,2번 작업을 0 ~ 256높이의 블록을 돌면서 모두 수행하고, 각 층마다 소요한 최소 시간을 저장한다.(단, 소유한 블록보다 쓴 블록이 많다면 continue)

import sys
input = sys.stdin.readline
N, M, B = map(int, input().split())
block = []
for _ in range(N):
    block.append(list(map(int, input().split())))

ans = int(1e9)
glevel = 0

for i in range(257):  # 땅 높이
    use_block = 0
    take_block = 0
    for x in range(N):
        for y in range(M):
            if block[x][y] > i:
                take_block += block[x][y] - i
            else:
                use_block += i - block[x][y]

    if use_block > take_block + B:
        continue

    count = take_block * 2 + use_block

    if count <= ans:
        ans = count
        glevel = i

print(ans, glevel)

Time Complexity:

땅의 최대 높이 256, 가로, 세로 각각 500 x 500 이다. 따라서, TC = O(256 * 500 * 500) = 64,000,000이다. python으로 돌리면 시간 초과다.. (1초에 대략 2000~2500만번이므로..) 그래서 pypy로 돌렸더니 AC를 받았다.