[BOJ] 18111. 마인크래프트(python)

📌문제

💪아이디어

이 문제는 시간초과떄문에 꽤나 애먹었던 문제였다. 시간 복잡도를 줄이기 위해
1) 땅을 이차원 배열에서 일차원 배열로 바꿔서 for문을 줄인다.
2) 땅의 높이를 입력받은 땅의 높이 min에서 max+1까지 검사한다.
등등 알고리즘을 바꾸려고 노력했는데 결국에는 언어를 python3이 아니라 pypy3로 바꾼 후 통과할 수 있었다.

	python3	pypy3
메모리사용	-	자주쓰는 코드를 캐싱 메모리사용↑
생산속도	별도의 컴파일과정이 있어 느림	빠름
실행속도	빠름	한줄씩 명령어를 처리해서 느림

</center>

간단한 코드에서는 python3가 메모리, 속도상에서 우세하고 복잡한 코드(반복)에서는 pypy3가 우세

1. 땅의 높이 가정하기
   땅의 높이는 0~256까지 가능하다고 해서 경우의 수를 모두 넣어 찾는다.
   

2. 땅의 높이 맞추기
   땅이 기준보다 높으면 블록을 파야하고 낮으면 블록을 쌓아야한다. 파면 인벤토리의 블록이 늘어나고 쌓으면 인벤토리의 블록이 사라진다. 쌓아야하는 블록이 인벤토리에 가지고 있는 블록보다 많으면 불가능하다.

3. 최소 시간 구하기
   땅을 파는데 걸리는 시간은 2초, 땅을 쌓는데 걸리는 시간은 1초이기 때문에 위에서 계산한 땅을 팠을 때 필요한 블록의 갯수를 땅을 파는 행위, 땅을 쌓았을 때 필요한 블록의 갯수를 땅을 쌓는 행위라 하고 총 걸리는 시간을 계산한다.
   

4. 땅의 최대 높이 구하기
   1번에서 정한 땅의 높이일때 최소 시간이라면 그 땅높이가 평탄화 작업에 걸리는 최소시간의 높이이다. 0~257까지 검사하므로 후반일 수록 높은 땅의 기준으로 검사한다. 앞에서 구한 최소시간과 같으면 땅의 최대 높이를 구할 수 있다.
   

🥂코드

import sys
input = sys.stdin.readline

N, M, B = map(int, input().split())
land = []
for _ in range(N):
    land += list(map(int, input().split()))

time = float('inf')
height = 0

for h in range(257):
    build_time = 0
    remove_blocks = 0
    add_blocks = 0

    for l in land:
        if l < h:
            remove_blocks += h - l
        else:
            add_blocks += l - h

    if remove_blocks > add_blocks + B:
        continue

    build_time = remove_blocks + add_blocks * 2
    if build_time <= time:
        time = build_time
        height = h

print(time, height)