[백준/브루트포스] - 18111 마인크래프트 (Python)

문제 링크

풀이과정

먼저 1부터 256까지의 타겟 높이로 쌓아야할 개수(mincount)와 없애야할 개수(maxcount)를 센 다음, maxcount+b보다 mincount가 더 큰 경우(없애는 블록+가지고있는 블록<쌓아야할 개수) 불가능한 것이므로 continue를 통해 뛰어넘고 가능하다면 mincount+(maxcount*2)가 time보다 작은 경우 time을 갱신해주는 식으로 구현했다. python으로 풀려고하니 시간초과가 많이 나서.. 여러모로 까다로웠던 문제였다.
(python으로 풀면 시간초과가 나 PyPy3로 제출하였다.)

코드

import sys #o(n*m*256)라 시간초과 남
n,m,b=map(int, sys.stdin.readline().strip().split())
l1=[list(map(int, sys.stdin.readline().split())) for _ in range(n)]

time,high=100000000000,0
for target in range(257):
    mincount, maxcount=0,0
    for i in range(n):
        for j in range(m):
            if l1[i][j]>target: #target보다 큰 거 숫자세기 (없애야할 개수)
                maxcount+=l1[i][j]-target
            else: #target보다 작은거 숫자세기 (쌓아야할 개수)
                mincount+=target-l1[i][j]

    if mincount>maxcount+b: #불가능한 경우 뛰어넘기
        continue
        
    if mincount+(maxcount*2)<=time: #쌓아야할거 + 없애야할거*2 <= 시간
        time=mincount+(maxcount*2) #시간갱신
        high=target

print(time, high)