[Python] 18111번 마인크래프트

문제

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

풀이과정

내가 생각해본 것

• 1초
  인벤토리에서 블록 하나를 꺼내서 좌표에 가장 위에 있는 블록위에 놓는다. → 좌표의 블록 +1, 인벤토리 -1
  
• 2초
  좌표 가장 위에 있는 블록을 제거하고 인벤토리에 넣는다. → 좌표의 블록 -1, 인벤토리 +1
  
• 제한
  n,m ≤ 500 이고 높이는 256을 초과할 수 없다.
  
• 과정
  땅 높이의 기준을 정해야 한다.
  → 가장 작은 값 ~ 가장 큰 값 사이에서 적당한 값을 찾아야 한다.
  기준보다 높으면 깎고, 기준보다 낮으면 쌓아야한다.
  인벤토리에 있는 블럭들로 쌓을 수 있는지 확인해야한다.
  → 블록이 비슷하다면 깎아서 높이를 낮춰야 한다.
  같은 시간이라면 높이가 가장 높은것을 출력한다.
  

고민하는 시간이 너무 길어져서 다른 코드를 참고했다.

정답1

import sys

# 입력 구간
N, M, B = map(int, sys.stdin.readline().split())  # 세로 가로, 인벤토리에 있는 블록 개수
ground = []
for i in range(N):
    ground.append(list(map(int, sys.stdin.readline().split())))
# print(ground)
min_h = min(min(ground))
max_h = max(max(ground))

# print(min_h, max_h)
res = [1e9, 0] # 최종 시간(무한대로 초기화)과 최종 높이 저장 

for v in range(min_h, max_h + 1):
    up = 0  # 높이가 v보다 작은 지형에서 필요한 블록의 개수 저장
    down = 0  # 반대로 높은 지형에서 제거할 블록의 개수 저장
    time = 0

    for i in range(N):
        for j in range(M):
            diff = ground[i][j] - v 
            if diff > 0:
                down += diff
            else:
                up -= diff

    if down + B >= up: 
        time = down * 2 + up # 총 시간 
        if res[0] >= time: # 최소 시간 갱신 
            res[0] = time
            res[1] = v # 최소시간일 때의 현재 높이 

print(*res) # 각 요소를 공백으로 구분하여 출력

→ python으로 제출할경우 시간초과가 발생하고, pypy3로 출력하면 통과한다.

for i in range(N):
        for j in range(M):
            diff = ground[i][j] - v  # 63 - 64일 경우 -1 -> 쌓아 올려주어야 한다.
            if diff > 0:
                down += diff
            else:
                up -= diff

전부 돌아보는 코드이다. 예를들어, 63 - 64일 경우 -1 -> 쌓아 올려주어야 한다. -> else문

if down + B >= up:
        time = down * 2 + up
        if res[0] >= time:
            res[0] = time
            res[1] = v

→ 블록을 제거하고 싶을 때 사용하는 코드이며, 최소값을 갱신해준다.
쌓아올려야 할 경우에는 내 인벤토리에서 블록을 꺼내 사용할 필요가 있기 때문에
down해서 빼온 블록과 내 인벤토리의 블록개수와 같거나 커야만 쌓아올릴 수 있다.

정답2

python으로도 통과할 수 있는 코드를 찾아보고 분석해보았다.

import sys

input = sys.stdin.readline
# 입력구간
N, M, B = map(int, input().split())

ground = []
HEIS = [0 for _ in range(257)]  # 높이의 빈도 0 ~ 256

for n in range(N):
    T = list(map(int, input().split()))  # 한 줄씩 입력받는 것
    for m in range(M):
        HEIS[T[m]] += 1
    ground.append(T)

m_res, h_res = 1e9, 0  # 최소시간, 해당 높이
for h in range(257):
    up = 0
    down = 0
    for b in range(257):
        if h > b: # 현재 높이(h)가 블록의 높이(b) 비교 
            up += (h - b) * HEIS[b] # 쌓아야 하는 정도 * 빈도수 
        else:
            down += (b - h) * HEIS[b]
    inven = B + down - up
    if inven < 0: # 가지고 있는 블록의 개수 확인
        continue
    t = down * 2 + up
    if t <= m_res:
        m_res = t
        h_res = h

print(m_res, h_res)

• 입력 부분

for n in range(N):
    T = list(map(int, input().split())) # 한 줄씩 입력받는 것 
    for m in range(M):
        HEIS[T[m]] += 1 
    ground.append(T)

예제 입력

3 4 1
64 64 64 64
64 64 64 64
64 64 64 63

여기서 HEITS를 출력해보면 많은 빈도수들 중에 1,11이 출력되는데 이는 63번이 1개, 64번이 11개 있기 때문이다. → 63번째에 1, 64번째에 11번이 입력된 것이다.

• 초기화

m_res, h_res = 1e9, 0

무한으로 설정하는 이유 : 비교 과정에서 올바르게 동작할 수 있기 때문이다.

• 처리하는 과정

  for h in range(257):
      up = 0
      down = 0
      for b in range(257):
          if h > b: # 현재 높이(h)가 블록의 높이(b) 비교 
              up += (h - b) * HEIS[b] # 쌓아야 하는 정도 * 빈도수 
          else:
              down += (b - h) * HEIS[b]
      inven = B + down - up
      if inven < 0: # 가지고 있는 블록의 개수 확인
          continue
      t = down * 2 + up
      if t <= m_res:
          m_res = t
          h_res = h

  → 빈도 수를 이용해서 한번에 계산하여 쌓아야 하는 개수와 파야하는 블록의 개수를 한번에 구한다.
  
• 정답 1 보다 빠른이유
  1. 높이 빈도를 미리 지정하여 각 높이가 몇번 등장하는지 빠르게 파악할 수 있다.
  2. 빈도수를 이용해서 2중 for문까지만 사용했다.

안보고 제한시간내에 문제를 구현할 수 있는 날이 오기를..