2023.01.20 마인크래프트 백준[파이썬]

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

18111번: 마인크래프트

 

이번 문제는 진짜 계속 시간 초과 나서 머리 잡고 있다가 pypy로 돌리니 시간초과 안나서 해결 된... 마음에 안드는 풀이법 밖에 없다. 이후 찾아 보니깐 dict로 풀거나 다른걸로 풀던데 나중에 정리 해봐야겠다.

import sys
input = sys.stdin.readline

n, m , inven = map(int,input().split())
max_high = 0
land = []
sums = 0


for _ in range(n):
    saves = list(map(int,input().split()))
    if max(saves) > max_high:
        max_high = max(saves)
    sums += sum(saves)
    land.append(saves)

sums = (sums+inven) // (n*m) # 전체흙의 개수를 전체 칸 개수로 나누면 그게 만들 수 있는 최대 높이이다.

if sums < max_high:
    max_high = sums # 그 높이가 가장 높은 거 보다 높으면 그냥 가장 높은 곳 기준으로 쌓는게 이득이다.

counters = 0
up_time = 0
for high in range(max_high,-1,-1): # 가능한 가장 높은 곳에서부터 내려온다. 
    down_time = 0    
    for i in range(n):
        for j in range(m):
            a = land[i][j] - (high - 1) # 높이와 현재 쌓여있는 높이의 차이
            if a < 0: # 흙이 부족하면 더 쌓는시간을 더한다.
                down_time += -a # 음수니깐 - 붙여서 더하기
            elif a > 0: #흙이 더 많으면 흙을 부순다.
                down_time += a * 2 # 흙을 제거하는 연산이니깐 *2를 해서 더하기
            if high == max_high: # 처음 시작 할 때만 현재 높이 계산
                b = land[i][j] - (high) # 한칸 낮은 곳의 높이의 차이 
                if b < 0: #아래층도 똑같이 계산 해준다
                    up_time += -b
                elif b > 0:
                    up_time += b * 2
    if up_time <= down_time: # 아래층으로 만드는 시간보다 위층을 만드는 시간이 덜 걸리면 그게 시간 최소값이다
        print(up_time, high)
        break
    up_time = down_time

1번째 아이디어는 모든 흙의 개수랑 inven 에 있는 흙의 개수 를 칸의 개수로 나누면 나올 수 있는 최대 높이가 나온다.

그 높이랑 현재 가장 높이 쌓여있는 흙의이랑 해서 더 낮을 걸 최대 높이로 생각했다.

최대 높이에서 부터 내려가면서 그 층으로 만드는데 드는 시간과 그 아래 층으로 만드는데 드는 시간중 크기 비교를 했다.

2번째 아이디어는 만약 아래층이 더 적은 시간으로 만들어 진다면 그 아래층도 확인 해봐야 하고 만약 아래층보다 적은 시간안에 만들어진다면 그 층이 최소 시간이다 라고 생각 했다. 

이유는 내려갔는데 시간이 줄어든다는 것은 흙을 지우는 것보다 쌓는게 시간이 더 많이 걸리는 거고 반대로 시간이 늘어난다는 것은 그 아래로는 흙을 파는 거, 즉 시간이 늘어날 일 밖에 없으니 아래층이 시간이 늘어날 때가 가장 최소시간에 가장 높은 층이라고 생각했다.