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

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

18111번: 마인크래프트

 

 

# 조건

• 1 x 1 x 1 크기의 블록들로 이루어진 3차원 세계
• 땅을 고르게 해야 집을 지을 수 있다.
• 세로 N, 가로 M 크기의 집터

1. 좌표 (i, j)의 가장 위에 있는 블록을 제거하여 인벤토리에 넣는다.
2. 인벤토리에서 블록하나를 꺼내어 좌표 (i, j)의 가장 위에 있는 블록 위에 놓는다.

• 1번 작업은 2초, 2번 작업은 1초
• 인벤토리에 B개의 블록 들어있고 256의 높이 초과 불가

걸리는 최소 시간과 땅의 높이를 출력

 

# 접근 방법

• 처음 -> 가장 max숫자부터 1까지 맞춰주며 전부니 시간 초과
• 브루트포스지만 안되는 조건들을 쳐내주면 python으로 통과된다.
• min부터 max 높이를 설정해주고, 평탄화 작업을 인벤토리 + (추가로 발생한 block 개수)가 (꺼내쓴 block) 수보다 크다면 작업이 가능

 

시간초과 - pypy통과

import sys
N, M, B = map(int,input().split())
block = []
for _ in range(N):
    block.append([int(x) for x in sys.stdin.readline().rstrip().split()])
# 최대값 크게 설정
ans = int(1e9)
# 땅 높이
glevel = 0

for i in range(257): #땅 높이
    use_block = 0
    take_block = 0
    # 평탄화 높이 보다 높다면 take에 기록
    # 낮다면 use 에 기록
    for x in range(N):
        for y in range(M):
            if block[x][y] > i:
                take_block += block[x][y] - i
            else:
                use_block += i - block[x][y]

	# 사용한 블록이 take + 인벤토리보다 많다면 다음 반복문으로 continue
    if use_block > take_block + B:
        continue
	# 내가 만들수 있는 평탄화 높이라면 count 기록 해준다.
    count = take_block * 2 + use_block

	# 시간 최소값과, 그 때의 평탄화 높이 기록
    if count <= ans:
        ans = count
        glevel = i

print(ans, glevel)

 

python 통과 1

from collections import defaultdict  
#2차원이긴 한데 2차원으로 할 필요 없음  
N,M,B = map(int,input().split())  
grid = []  
for i in range(N):  
    grid += [*map(int,input().split())]  
#되로록 쌓아 올리면서 평탄화 하는게 나음.  
ans = defaultdict(list)  
hist = []  
for i in range(min(grid),max(grid)+1): #모든 평탄화 가능 경우의수 다보기  
    fills = time = 0; mine = B  
    # 양수면 쌓아야 하는 수, #음수면 깎아야 하는 수  
    for j in grid: 
	    #fills = 필요한 블록수 ,mine = 생기는 블록수 + 원래 보유 블록  
        pivot = i - j  
        if pivot >= 0: fills += pivot; time += pivot  
        else: mine -= pivot; time -= 2*pivot  
        if hist and time > hist[-1]: break  
    else:  
        if fills <= mine: #가능  
            ans[time].append(i)  
            hist.append(time)  
        else: #불가능  
            continue  
mini = min(ans)  
print( mini,max(ans[mini]) )

 

 

python 통과 2

n,m,b = map(int,input().split())  
gr = []  
for _ in range(n): gr += map(int,input().split())  
h, tm = 0, 100000000  
dic = dict()  
# 딕셔너리로 각 높이의 블록 수를 기록해준다.
for a in gr: dic[a] = 1 if dic.get(a) == None else dic[a]+1  
# 범위는 가장 낮은 곳부터 가장 높은 곳 까지
for k in range(min(gr), max(gr)+1):  
	# 인벤토리 + 현재 블록의 높이를 모두 합친 것이 전체 배열 * 평탄화시킬높이보다 크다면
    if sum(gr)+b >= k*m*n:  
        ktm = 0  
        for d in dic:  
	        # 필요한 블록 수 = (현재높이 - 평탄화시킬 높이) * 같은 높이의 블록 수
            dff = (d - k)*dic[d]  
            # (d-k)가 양수라면 더 높은 것이니 시간이 2초, 아니라면 1초
            ktm += dff*2 if dff > 0 else -dff  
        # 
        if ktm <= tm: tm, h = ktm, k  
print(tm, h)