백준 18111 - 마인크래프트 (Python3)

코드

풀이 1 (Pypy3)

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

ground = [list(map(int, input().split())) for _ in range(N)]

time = 1e10
height = 0

# 높이의 최대가 256이므로 목표 높이의 범위는 0 ~ 256
target_heights = 257
for target in range(target_heights):
    
    # 조건에 맞게 사용한 블록의 개수
    # 새로 추가 (1초 소요)
    push_block = 0
    
    # 제거 (2초 소요)
    pop_block = 0
    
    for j in range(N):
        for k in range(M):
            if ground[j][k] < target:
                push_block += (target - ground[j][k])
            else:
                pop_block += (ground[j][k] - target)
                
    # 사용한 블록 > 인벤토리에 새로 들어온 블록 + 기존에 가지고 있는 블록인 경우
    # 사용해야하는 블록의 개수가 당연히 (기존 블록 개수 + 새로 들어온 개수)보다
    # 많아야만 작업 자체를 마무리 할 수 있으므로
    # 그거보다 작은 경우에서는 반복을 넘어간다
    if push_block > pop_block + B:
        continue
        
    total_time = push_block + (pop_block * 2)
    
    if total_time <= time:
        time = total_time
        height = target

print(time, height)

풀이 2 (Pypy3)

# 조건 1 : 블록 제거하고 인벤토리에 넣음 (2초 소요)
# 조건 2 : 블록을 새로 위에 얹음 (1초 소요)

N, M, B = map(int, input().split())
ground = [list(map(int, input().split())) for _ in range(N)]
INF = int(1e9)

# 블록의 최소 높이와 최대 높이
lo = min([min(x) for x in ground])
hi = max([max(x) for x in ground])

# target
def _mtg(ground, target, B):
    c1 = 0
    c2 = 0
    
    for i in range(N):
        for j in range(M):
            
            # 좌표 땅과 목표 높이의 차이
            block = ground[i][j] - target
            
            # 높이 차이가 양수 => 조건 1
            if block > 0:
                B += block
                c1 += 2 * block
            else:
                c2 += -block
            
    # 여기서 B의 값은 기존의 블록 + 새로 채굴한 블록이다
    # 즉, 풀이 1번의 조건과 동일하다
    if B < c2:
        return INF
    return c1 + c2

time = INF  
height = 0
    
# 가장 높은 높이부터 아래로 내려가면서 반복
# 아래로 내려가면서 같은 값이 나와도 처음 초기화 된 값이 그대로 남아있다
for target in range(hi, lo-1, -1):
    
    tot = _mtg(ground, target, B)
    
    if time > tot:
        time = tot
        height = target
        
print(time, height) 

문제 해설

브루트포스 문제이다. 개인적으로 브루트포스 문제에 정말 취약하다. 문제 이해도 어려웠지만 코드 구현화가 제법 어려워 구글링을 통해서 이해를 하고 내 것으로 만드려고 계속 노력하였다.

참고 유튜브