[Python] 백준 18111 마인크래프트

문제

 

 

 우리의 목적은 이 집터 내의 땅의 높이를 일정하게 바꾸는 것이다.

1. 좌표 (i, j)의 가장 위에 있는 블록을 제거하여 인벤토리에 넣는다.
2. 인벤토리에서 블록 하나를 꺼내어 좌표 (i, j)의 가장 위에 있는 블록 위에 놓는다

1번 작업은 2초가 걸리며, 2번 작업은 1초가 걸린다. ‘땅 고르기’ 작업에 걸리는 최소 시간과 그 경우 땅의 높이를 출력하시오.

 

✅ 작업을 시작할 때 인벤토리에는 B개의 블록이 들어 있다. 땅의 높이는 256블록을 초과할 수 없으며, 음수가 될 수 없다.

 

 

입력

• 첫째 줄: N, M, B
• 둘째 줄: N개의 줄에 각각 M개의 정수로 땅의 높이가 주어진다. 땅의 높이 = ( 256보다 작거나 같은 자연수 or 0 )

 

출력

땅을 고르는 데 걸리는 시간과 땅의 높이 출력( 답이 여러 개 있다면 그중에서 땅의 높이가 가장 높은 것을 출력 ) 

 

 

 

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

18111번: 마인크래프트

---

풀이

★Keypoint : 브루트포스 알고리즘

 

높이를 지정하고 해당 높이까지 필요한 블록의 개수나 남는 개수를 계산한 값을 가지고 있는 블록 수와 비교하여 최적의 값을 구하는 로직으로 문제를 해결해야 합니다.

 

 

<Try CODE>

N, M, B = map(int,(input().split()))
ground = []
for _ in range(N):
  ground.append(list(map(int, input().split())))

max_num = max(max(row) for row in arr)

if ground[N-1][M-1] == max_num: #제일 높은 수라면
  if B >= (N*M -1):
    time = (N*M -1)
    print(time, max_num)
  else:
    while ground[N-1][M-1] != ground[N-1][M-2]:
      ground[N-1][M-1] += 1
      count += 1
    time = count * 2
    print(time, )
else: #다른 수들이 높으면
  if B >= (ground[N-1][M-2] - ground[N-1][M-1]):
    time = (ground[N-1][M-2] - ground[N-1][M-1])
  else:
    while ground[N-1][M-1] != ground[N-1][M-2]:
      ground[N-1][M-1] += 1
      count += 1
    time = count * 2

--> 위 코드는 문제를 해결하지 못했습니다.

 

 

<문제 해결 오류>

: 문제에 나와있는 출력예제에서 ground[N-1][M-1] 의 값만 높이가 다른데, 실제로 입력값은 그러지 않지만 그렇다고 오해하여 코드를 제대로 작성하지 못했습니다

-> ground 배열을 모두 돌면서 확인하는 code 작성해야 합니다

 

블록의 최대 크기가 256이므로 높이를 0부터 256까지 돌면서 가장 적정 높이를 지정하여 블록 개수와 비교해야 합니다.

문제에서 최소 시간을 구해야 한다고 했으므로 2번작업 즉, 블록의 개수가 추가로 필요한 낮은 높이를 우선으로 생각해야 하기 때문에 오름차순으로 for문을 돌아야 합니다. (만약, 내림차순으로 for문을 돌면 최적의 값을 구할 수 없습니다)

 

 

 

<최종 CODE>

#240408 백준 18111 마인크래프트
import sys

N, M, B= map(int, sys.stdin.readline().split())
ground = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
time = 1e9
final = 0

for height in range(257):    #높이가 높을수록 좋으니 최대 높이부터 확인 
    extra, short = 0, 0    #튀어나온 블록(남는 블록), 부족한 블록
    for i in range(N):
        for j in range(M):
            if ground[i][j] <= height:
                short += height - ground[i][j]
            else: 
                extra += ground[i][j] - height
        
    #인벤토리 개수 확인
    if extra + B >= short:
        if (extra * 2) + short <= time: #최소 시간인지 확인
            time = (extra * 2) + short #시간 갱신
            final = height


print(time, final)

 

 

 

회고

처음에는 왜 오름차순으로 for문을 돌아야 하는지 많은 고민을 했습니다. 값이 여러 개일 때 가장 높은 답을 출력하는 것은 후순위이고 우선 최소 시간을 고려해야 한다는 것을 망각해서 시간을 소비했던 것 같습니다! 문제 풀이 할 때, 상세한 조건을 인지한 후 코드를 작성하는 습관을 더 들여야겠습니다..