BOJ_18111 : 마인크래프트

👉 문제링크

18111번: 마인크래프트

---

---

🔸 문제 분석 🔸

• 땅 고르기 작업의 최소시간이며 가장 높이가 높은 상태의 시간과 높이를 출력한다.

🔸 코드 🔸

# python3 : 시간초과 , pypy3 : 통과
import sys

n, m, b = map(int, sys.stdin.readline().split())
arr = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]

answer = sys.maxsize
index = 0

for floor in range(257): # (1)
    up, down = 0, 0

    for i in range(n): 	 # (2)
        for j in range(m):
            if arr[i][j] >= floor:	# (3)
                up += arr[i][j] - floor
            else:			# (4)
                down += floor - arr[i][j]
    
    if b + up >= down and down + (up * 2) <= answer: # (5)
        answer = down + (up * 2)
        index = floor

print(answer, index)

🔸 코드 해석 🔸

• (1) : 층 수를 0부터 256까지 증가시키며 고르기 작업이 가능한지, 최소시간인지 확인한다
  • (2) : 입력받은 높이 정보를 순회한다
    • (3) : 블록의 높이가 현재 층 수(floor)보다 크다면 크 차이를 up에 합산
    • (4) : 블록이 높이가 현재 층 수(floor)보다 자가다면 크 차이를 down에 합산
    • up : 빼야하는 블록
    • down : 더해야하는 블록
  • (5) : 기존 블록(b)와 빼야하는 블록(up)의 합이 더해야하는 블록(down)보다 크거나 같아야 땅고르기 가능.
  • (5) : 걸리는 시간이 저장된 시간보다 작거나 같으면 최신화 시켜줌
    • 걸리는 시간(answer) : 더하기(1초씩) + 빼기(2초씩)
    • 땅고르기를 진행한 높이 : index

🔸 오답 코드 🔸

import sys
input = sys.stdin.readline

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

strs = ""
for i in range(N):
    strs += input().rstrip() + " "
arr = list(map(int,strs.split()))

all_same = False
answer = 0

while not all_same:
    if len(set(arr)) == 1:
        all_same = True
        break

    if not all_same:
        hi = max(arr)
        low = min(arr)
        hc = arr.count(hi)
        lc = arr.count(low)
        if hc < lc or B < lc:
            arr = list(map(lambda x: x-1 if x==hi else x, arr))
            B += hc
            answer += 2 * hc
        else:
            arr = list(map(lambda x: x+1 if x==low else x, arr))
            B -= lc
            answer += lc
print(answer)

🔸 코드 해석 🔸

• python3, pypy3 모두 시간초과가 나오는 코드이다.
• 블록 높이 배열에서 최댓값과 최솟값을 지속적으로 매칭하며 땅을 고르는 방식이다.
• N, M의 최대값이 500이므로 너무 많은 반복수를 가진다.

---

🔸 end 🔸

• 문제 접근을 잘못해서 결국 답을 찾아봤다. (답안 포스팅)
• 문제 태그에 브루트 포스가 있어서 어느 부분을 모두 찾아봐야할까 고민하다가, 높이가 일정해질때까지 평탄화를 반복하는 방식을 선택했지만 틀렸다...
• 높이를 0부터 256까지 높여가며 최소시간 중 가장 높인 층을 출력하는 방식으로 풀었어야했다.
• 시간초과는 해결하기 참 머리아프고 내 코드를 계속 의심해야한다는게 풀이가 어려운 것 같다. 좀더 근거 있게 풀어가야 할 것 같다.
• python3는 시간초과가 나서 pypy3로 해야한다는게 또다른 아쉬움으로 남았다.