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

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

18111번: 마인크래프트

---

아이디어

1. 브루트 포스

• 문제에서 높이 이가 256까지 그리고 N, M이 500까지가 최대다.
• 256*500*500 = 64000000이므로 1초 안에 가능하다 생각..

2. 시간 초과

• 브루트 포스로 가능하다 생각했는데 계속 시간 초과가 걸렸다.
• 다른 사람들이 짠 코드를 확인해 보니 elif가 아닌 else를 사용했다.
• pypy로 통과했다.
• else와 elif가 시간 차이가 많이 난다는 것을 처음 알았다.

 

---

코드 설명

for i in range(257): #땅 높이
    use_block = 0
    take_block = 0
    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]

    if use_block > take_block + B:
        continue

    count = take_block * 2 + use_block

    if count <= ans:
        ans = count
        glevel = i

각 도달하고 싶은 높이마다 2차원 리스트를 탐색해준다.

 

블록 높이와 도달 높이를 비교해가며 가져온 블록(take_block), 사용한 블럭(use_block)에 블럭 개수를 추가해준다.

이후 총 사용한 블록과 가져온 블록 + 원래 있던 블럭 개수를 비교해서 도달 높이로 만드는 게 가능한지 확인한다.

 

가능하다면 걸리는 시간을 계산하고 최솟값 비교를 해준다.

 

---

전체 코드

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
    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]

    if use_block > take_block + B:
        continue

    count = take_block * 2 + use_block

    if count <= ans:
        ans = count
        glevel = i

print(ans, glevel)

else보다 elif 가 연산을 더 하니까 시간이 더 걸린다고는 생각했지만 시간 초과가 뜰 정도로 차이 날줄 몰랐다.

골드 이상 문제들을 풀다 보면 이런 식으로 시간 초과가 너무 자주 나온다. cpp로 넘어갈까 고민.