[백준 18111번] 마인크래프트 - python

문제 링크

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

18111번: 마인크래프트

풀이 

- 높이를 0부터 256까지 모든 경우의 수에 대하여 해당 높이로 맞출 때 걸리는 시간을 구해주었다. 

-  맞출 높이보다 작을 때 블록을 좌표에 놓아야 하므로 인벤토리에 있는 블록의 수에서 놓을 블록의 수 만큼 빼준다 
-  맞출 높이보다 크면 블록을 인벤토리에 넣어야 하므로 인벤토리에 있는 블록의 수에 넣을 블록의 수를 더해준다.

- 인벤토리에 있는 블록의 수가 음수면 블록의 수가 부족한 것이므로 고려하지 않는다.

- 인벤토리에 있는 블록의 수가 양수이고 이 때 걸리는 시간이 answer보다 작거나 같으면 값을 갱신해준다.

- 아래 코드를 Pypy3으로 실행할 경우 틀렸다고 나오고 Python3으로 실행할 경우 시간초과가 발생하였다. 

# 시간초과 
import sys
input = sys.stdin.readline

INF = int(1e9)

n, m, b = map(int,input().split())

graph = []

for i in range(n):
  graph.append(list(map(int,input().split())))

answer = INF
h = 0 

for i in range(257):
  cnt = 0 
  block = b
  
  for x in range(n):
    for y in range(m):
      # 맞출 높이보다 작을 때 블록을 좌표에 놓아야 한다 
      if i > graph[x][y] :
        block -= (i - graph[x][y])
        cnt += 1 
      # 맞출 높이보다 크면 블록을 인벤토리에 넣어야 한다 
      elif i < graph[x][y]:
        block += (graph[x][y] - i) 
        cnt += 2 
    
  if block >= 0 :
    if cnt <= answer :
      answer = cnt 
      h = i
    
print(answer, h)

- 따라서 블록 수 부분을 수정해주었다. 

- b_min : 인벤토리에서 뺄 블록 수 

- b_max : 인벤토리에 넣을 블록 수 

따라서 총 블록 수 block는 원래 인벤토리에 있던 블록 수 b + b_max 이다. 

만약 block < b_min 이라면 블록 수가 부족한 것이므로 continue

그렇지 않으면 걸리는 시간을 계산한다. 이 때 걸리는 시간은 2 * b_max +  b_min 이다. 

 이 때 걸리는 시간이 answer보다 작거나 같으면 값을 갱신해준다.

import sys
input = sys.stdin.readline

INF = int(1e9)

n, m, b = map(int,input().split())

graph = []

for i in range(n):
  graph.append(list(map(int,input().split())))

# 걸리는 시간 
answer = INF
# 높이
h = 0 
 
for i in range(257):
  # b_min : 인벤토리에서 뺄 블록 수 
  # b_max : 인벤토리에 넣을 블록 수
  b_min = 0
  b_max = 0

  for x in range(n):
    for y in range(m):
      # 맞출 높이보다 작을 때 블록을 좌표에 놓아야 한다 
      if i > graph[x][y] :
        b_min += (i - graph[x][y])
      # 맞출 높이보다 크면 블록을 인벤토리에 넣어야 한다 
      else :
        b_max += (graph[x][y] - i) 
  # 총 블록 수 
  block = b + b_max 
  # 블록수가 부족하면 
  if block < b_min :
    continue
  # 걸리는 시간 계산 
  t = 2 * b_max + b_min
  # 시간 작은 값으로 갱신, 같을 경우 높이가 높은 것으로 갱신 
  if t <= answer :
    answer = t 
    h = i 
    
print(answer, h)

- pypy3으로 통과, python3으로는 시간초과 발생 

- 모든 경우의 수에 대해 탐색을 마친 후 검사하는 것이 아니라, 중간에 검사하는 방식으로 고려해봐야 겠다