[Baekjoon] 18111번 : 마인크래프트 (Python, 구현, 브루트 포스)

[Baekjoon] 18111번 : 마인크래프트 (Python, 구현, 브루트 포스)

 

목차

 

 

 

 

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

18111번: 마인크래프트

코드 링크

https://github.com/stellaluminary/Baekjoon

GitHub - stellaluminary/Baekjoon

 

Python

 

시간 초과 - 방법 1 - 메모리 117404KB / 시간 688ms / 코드 길이 588B (PyPy3 통과)

 

최소 높이와 최대 높이에 대하여 주어진 면적의 높이차이를 구한다.

이후 block의 개수에 따른 값들을 변화해가며 0보다 클 때 시간과 높이를 저장한다.

다만 시간 초과가 나서 PyPy3에 대한 결과만 참으로 나타난다.

 

유의) 블록의 개수를 셀 때는 모든 면적에 대한 제거와 쌓기의 counting을 진행한 뒤 한 번에 처리해야한다.

그렇지 않으면 전체 면적기준으로 블록이 남는데 적다고 나오는 불상사가 나타날 수 있음(경험담....)

 

import sys
input = sys.stdin.readline

n,m,b = map(int, input().split())
l = [list(map(int, input().split())) for _ in range(n)]
res = [1e9, 0]

min_h = min(min(l))
max_h = max(max(l))

for v in range(min_h, max_h + 1):
    up = 0
    down = 0
    time = 0

    for i in range(n):
        for j in range(m):
            diff = l[i][j] - v
            if diff > 0:
                down += diff
            elif diff < 0:
                up -= diff

    if down + b >= up:
        time = down * 2 + up
        if res[0] >= time:
            res[0] = time
            res[1] = v

print(*res)