[백준] 18111번: 마인크래프트 / 파이썬

문제 링크

---

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

풀이 코드

---

import sys
n, m, b = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(n)]
idx = 0
dap = sys.maxsize

for floor in range(257):
    maxb, minb = 0, 0  

    for i in range(n):
        for j in range(m):
            if graph[i][j] > floor:  # 블록이 현재 층보다 높다면
                maxb += graph[i][j] - floor
            else:  # 아니라면
                minb += floor - graph[i][j]

    if maxb + b >= minb:  # 블럭수로 평탄화 가능여부 확인
        if maxb * 2 + minb <= dap:
            dap = maxb * 2 + minb
            idx = floor 

print(dap, idx)

코드 해석

---

브루트포스 알고리즘을 사용하였고 python을 사용하니 시간 초과가 나서 pypy를 사용하였다.

 

새로운 층을 만들어 한 층 씩 올려가며 비교하는 원리다.

0층부터 시작하여 256층까지 쌓으며

그 층을 만드는데 필요한 시간을 비교한다.

가장 짧은 시간이 걸리는 층을 고르면 끝

 

 

완전 상상도 못한 풀이법이었다.

시간 초과도 당황스러웠다...

체감 난이도: ★★★★☆