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

문제

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

풀이

256부터 0 높이의 모든 평탄화 케이스를 만들어 나가면서
걸리는 최소 시간과 그 높이를 구한다.

역순으로 탐색하는 이유는 문제 조건 중에 만약 걸리는 시간이 같다면
더 높은 땅의 케이스를 출력하라고 했기 때문에 역순으로 탐색한다면
추가적인 작업이 없어지기 때문이다.

평탄화 작업에서 땅을 깎을때는 블록을 저장해야하기 때문에
블록 값을 1 증가시킨디.

땅을 쌓을 때는 use_block이라는 사용 블록 수를 저장하는 변수에
값을 1 증가 시킨다.

평탄화 작업이 끝나고 사용 블록 수(use_Block)가 가지고 있는 블록 수(B) 보다
작으면 측정한 시간을 return 하고

그렇지 않으면 INF 를 반환한다.

N, M, B = map(int, input().split(" "))
board = []
for _ in range(N):
    board += list(map(int, input().split(" ")))
INF = int(10e9)
def check(lv, B, board):

    time = 0
    use_block = 0
    for board_lv in board:
        diff = board_lv - lv
        if diff > 0: # 땅 깎기
            time += 2 * diff
            B += diff

        if diff < 0: # 땅 쌓기
            time += -diff
            use_block += -diff

    return time if use_block <= B else INF


def solution(N,M,B,board):
    result_lv = 0
    result_time = INF
    for lv in range(256, -1, -1):
        check_time = check(lv, B, board)
        if check_time < result_time:
            result_lv = lv
            result_time = check_time

    return f'{result_time} {result_lv}'

print(solution(N,M,B,board))