🥚문제

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

• 구현
• 브루트포스 알고리즘

🥚입력/출력

🍳코드

# 출처: https://peisea0830.tistory.com/3
import sys
input = sys.stdin.readline

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

# 땅을 고르는 데 걸리는 시간과 높이 저장
min_time = float('inf')
max_height = 0

# 기준이 되는 높이 h (0 <= h <= 256)
for h in range(257):
    # 초기 블록 + 인벤토리에 추가할 블록의 개수 >= 사용해야하는 블록의 개수 -> h로 땅을 고를 수 있음
    in_block = 0
    out_block = 0
    for r in range(N):
        for c in range(M):
            if arr[r][c] > h:
                in_block += arr[r][c] - h
            else:
                out_block += h - arr[r][c]
    
    inventory = in_block + B
    if inventory < out_block:
        continue

    time = in_block * 2 + out_block
    if time <= min_time:
        min_time = time
        # 시간이 같을 때는 높이가 높은 순으로 출력하라는 조건에 맞게
        # for i in range(257)은 항상 i가 오름차순으로 돌기 때문에
        # 시간이 같아도 최종적으로는ㄴ 높이가 높은 순으로 나오게 된다
        max_height = h
            

print(min_time, max_height)

🧂아이디어

BFS

참고: https://peisea0830.tistory.com/3

• 어떻게 구현해야 할지, 시간을 어떻게 줄일 수 있을지 고민을 많이 했던 문제

• 땅을 어떤 높이로 해야할지? -> 0부터 256까지의 높이를 브루트포스로 검사해본다

• 위 참고 링크를 통해 "초기 블록 + 인벤토리에 추가할 블록의 개수 >= 사용해야하는 블록의 개수 -> h로 땅을 고를 수 있음" 임을 알게 되었다.

• 따라서, 높이 h를 만들려 할 때 추가할 블록 개수, 사용해야할 블록 개수를 각각 in_block, out_block으로 집계한다.

• in_block + B < out_block이면 현재 높이로 고를 수 없기 때문에 다음 높이를 검사한다.

• in_block + B >= out_block인 경우, 걸리는 시간 time은 in_block*2 + out_block .

• 마지막에 최소 시간, 최대 높이를 출력하기 위해 time < min_time이면 min_time = time, max_height = h로 갱신해준다.

  • 이때, h > max_height인지 검사하는 과정을 생략할 수 있는 이유는 for h in range(257)로, h는 늘 오름차순으로 검사되기 때문이다.