백준 18111 Python

• 처음에 내가 예제를 보고, 아 그냥 한번 쓱 보고 기존 블록 높이랑 다른 곳이 있으면 거기서 하나씩 블록을 가져오거나 부수면 되겠지 싶었다. dict 자료구조를 이용해 풀려고 했으나 이는 너무나 모호한 방법이어서 코드로 구현 할 수 없었다.

• 그래서 구글링을 통해 브루트포스 알고리즘 사용한 문제 해결 방식을 찾아봤다.

• 먼저 블록의 높이 범위는 0~256이기 때문에 각 높이를 기준으로 땅 전체를 탐색하는 것이다. 그러면서 높이의 기준에 따라 블록을 부수거나 쌓는 경우를 기록해 각 경우에 대한 결과를 기록하고 마지막에 기준 높이에 맞게 모든 블록을 쌓을 수 있는지 확인했다.

• 좀 더 시각적으로 설명하면 2차원 좌표에 우리가 탐색하고자 하는 땅들의 정보가 일렬로 있다고 가정하자. 그때 우리가 정한 높이(h)를 y절편에 그어 해당 기준선에 미달하는 땅은 블록을 쌓아야 할 곳, 기준선 보다 높은 곳은 블록을 부셔야 할 곳이다.
  

• 추가로 문제풀이를 참고한 블로그와 백준에 반례코드를 정리해주신 고마운 분들의 링크를 마지막에 달아 두었다. 이 글을 보는 분들도 해당 사이트들이 도움이 됐으면 한다.

import sys
input = sys.stdin.readline

# 문제 데이터 입력 받기
N, M, B = map(int, input().split())
LAND = [list(map(int, input().split())) for _ in range(N)]

# 브루트포스트 탐색 시작
answer_time = sys.maxsize
answer_h = 0
# 블록의 높이 범위는 0 ~ 256
for h in range(257):
    build = 0
    remove = 0
    for row in range(N):
        for col in range(M):
            work = LAND[row][col] - h
            # 우리기 부숴야될 블록수
            if work > 0:
                remove += work
            # 우리가 지어야될 블록수
            elif work < 0:
                build -= work
    # 부순 블록 + 가지고 있는 블록수가 지어야될 블록수보다 많다면
    if remove + B >= build:
        time = (remove * 2) + build
        if answer_time >= time:
            answer_time = time
            answer_height = h

print(answer_time, answer_height)


''' 참고 사이트
https://codecollector.tistory.com/678
https://www.acmicpc.net/board/view/86190
'''