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

[초기 접근 방법]

1.

모든 땅을 고르게 한다.

min ~ max 까지 땅의 높이를 고르게 했을 때, 소요 시간을 파악한다.

이전 소요 시간보다 크면 멈추고 출력 (최적화)

 

2.

시간을 계산한다.

if n > k (목표 높이가 높을 때)

     n의 높이로 설정했을 때, n-k 쌓을 블록이 필요 → 1

elif n < k (목표 높이가 낮을 때)

     k-n 블록을 제거 → 2

 

3.

B + push < need

n 높이로 고르게 만드는 건 불가능

 

 

[생각]

- 완전 탐색 문제

 

- 파이썬으로 제출할 때, elif로 조건 처리하게 되면 시간초과가 난다.

   else 로 256MN 처리를 줄여줘야 통과할 수 있다.

 

 

[코드]

# 풀이 시간 : 30분
# 시간복잡도 : O(256MN)
# 공간복잡도 : O(MN)
# 참고 : -

# elif else 문으로 시간초과 방지
# 동일 시간 time 처리
# minV, maxV를 구하지 않고 256번 고정 반복

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

time = float('inf')
for k in range(257):
    push = 0
    need = 0
    for i in range(N):
        for j in range(M):
            if board[i][j] > k:
                push += (board[i][j] - k)
            else:
                need += (k - board[i][j])

    # B + push에 비해 need가 크다면 해당 높이는 만족할 수 없음 → 더 깎아야 함
    if B + push < need:
        continue

    if time >= push * 2 + need * 1:
        time = push * 2 + need * 1
        high = k

print(time, high)