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

문제

18111번: 마인크래프트

포인트

문제 자체는 크게 어려운 문제가 아니나, 별 생각없이 3중 for문이 되버리면 시간이 빡빡해 파이썬으로 풀기에는 시간초과가 나와 다소 어려울 수 있다. 이럴 경우 pypy3에선 맞을테니 제출 방법을 바꿔보아도 좋다.

 

코드

python

import sys
input = sys.stdin.readline

N, M, B = map(int, input().split())
graph = {}

for _ in range(N):
    for i in  list(map(int, input().split())):
      if i in graph:
          graph[i] += 1
      else:
         graph[i] = 1

high = max(graph.keys())
low = min(graph.keys())

short_time = int(1e9)
ground = 0
for i in range(low, high + 1):
    inven = 0
    plant = 0
    for key, value in graph.items():
       if key > i:
          inven += (key - i) * value
       else:
          plant += (i - key) * value
    
    if inven + B < plant:
       continue
    else:
       time = (inven * 2) + plant
       if short_time >= time:
          short_time = time
          ground = i
print(short_time, ground)

pypy3

import sys
input = sys.stdin.readline

N, M, B = map(int, input().split())
graph = []

high = -1
low = 260

for _ in range(N):
    n =list(map(int, input().split())) 
    graph.append(n)
    high = max(max(n), high)
    low = min(min(n), low)

short_time = int(1e9)
ground = 0
for i in range(low, high + 1):
    inven = 0
    plant = 0
    for x in graph:
        for j in x:
            if j > i:
              inven += j - i
            else:
              plant += i - j
    
    if inven + B < plant:
       continue
    else:
       time = (inven * 2) + plant
       if short_time >= time:
          short_time = time
          ground = i
print(short_time, ground)

해설 

먼저 코드는 최대/최소 높이를 구해서 for 문을 돌리고 높이의 차이를 넣고 시간 중 작은 시간을 구해주는 방식으로 둘다 동일하다.

python 코드에서는 속도를 위해 기본 속도가 빠르고 for를 이중까지만 써도 되는 딕셔너리를 사용하였고, pypy3에서는 속도를 줄이기위해 graph[x][y](인덱스)방식 대신 바로 출력하여 나올수 있게 해주었다.