2022.02.25 [백준] (python 파이썬) 마인크래프트

 

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

18111번: 마인크래프트

---

풀이

이 문제를 어떻게 풀어야 할까 고민했지만 전체를 확인하는 방법 말고는 생각이 나지 않았다.

그래서 모든 경우의 수를 체크했고 python3로 제출하니 시간초과,,,,,

여기서 시간복잡도를 줄일 방법이 생각이 나지않아 pypy3로 제출하니 통과했다...!

 

우선 최소시간을 저장할 변수를 지정했다. 변수 초기 값은 가장 오래걸리는 시간+1을 했다.

그리고 모든 높이를 확인하기 위해 0~256까지 도는 for문을 돌렸고 쌓아야할 블럭 수를 저장할 up, 빼야할 블럭 수를 저장할 down을 지정했다. 그리고 다시 2중 for문을 이용해 각 좌표를 돌면서 해당 높이i와 비교해서 블럭 수를 체크했다. 

16번째 줄에서 이미 가지고 있는 블럭+뺀 블럭 수가 쌓아야 할 블럭수보다 작으면 해당 높이는 만들 수 없기 때문에 continue를 이용해 해당 높이for문을 넘겨주었다. 

해당 높이를 만들기 위한 시간을 구한 뒤 min_time과 비교하여 작거나 같으면 값을 바꿔주었다. 이렇게 하면 낮은 높이부터 for문이 돌기 때문에 같은 시간이 걸리면 더 높은 값이 저장되어 문제에 주어진 조건을 만족할 수 있다.

n,m,b=map(int,input().split())
graph=[list(map(int,input().split())) for _ in range(n)]
min_time=2*500*500*256+1
height=0
 
for i in range(257):
    up=0
    down=0
    for j in range(n):
        for k in range(m):
            if graph[j][k]<i:
                up+=i-graph[j][k]
            elif graph[j][k]>i:
                down+=graph[j][k]-i
    block_cnt=b+down
    if block_cnt<up:
        continue
    time=2*down+up
    if min_time>=time:
        min_time=time
        height=i
print(min_time, height,sep=' ')