18111번 - 마인크래프트

시간제한 : 1초(추가 시간 없음)
메모리 제한 : 1024MB

---

문제

팀 레드시프트는 대회 준비를 하다가 지루해져서 샌드박스 게임인 ‘마인크래프트’를 켰다. 마인크래프트는 1 × 1 × 1(세로, 가로, 높이) 크기의 블록들로 이루어진 3차원 세계에서 자유롭게 땅을 파거나 집을 지을 수 있는 게임이다.

목재를 충분히 모은 lvalue는 집을 짓기로 하였다. 하지만 고르지 않은 땅에는 집을 지을 수 없기 때문에 땅의 높이를 모두 동일하게 만드는 ‘땅 고르기’ 작업을 해야 한다.

lvalue는 세로 N, 가로 M 크기의 집터를 골랐다. 집터 맨 왼쪽 위의 좌표는 (0, 0)이다. 우리의 목적은 이 집터 내의 땅의 높이를 일정하게 바꾸는 것이다. 우리는 다음과 같은 두 종류의 작업을 할 수 있다.

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

1번 작업은 2초가 걸리며, 2번 작업은 1초가 걸린다. 밤에는 무서운 몬스터들이 나오기 때문에 최대한 빨리 땅 고르기 작업을 마쳐야 한다. ‘땅 고르기’ 작업에 걸리는 최소 시간과 그 경우 땅의 높이를 출력하시오.

단, 집터 아래에 동굴 등 빈 공간은 존재하지 않으며, 집터 바깥에서 블록을 가져올 수 없다. 또한, 작업을 시작할 때 인벤토리에는 B개의 블록이 들어 있다. 땅의 높이는 256블록을 초과할 수 없으며, 음수가 될 수 없다.

---

입력

첫째 줄에 N, M, B가 주어진다. (1 ≤ M, N ≤ 500, 0 ≤ B ≤ 6.4 × 107)

둘째 줄부터 N개의 줄에 각각 M개의 정수로 땅의 높이가 주어진다. (i + 2)번째 줄의 (j + 1)번째 수는 좌표 (i, j)에서의 땅의 높이를 나타낸다. 땅의 높이는 256보다 작거나 같은 자연수 또는 0이다.

---

출력

첫째 줄에 N, M, B가 주어진다. (1 ≤ M, N ≤ 500, 0 ≤ B ≤ 6.4 × 107)

둘째 줄부터 N개의 줄에 각각 M개의 정수로 땅의 높이가 주어진다. (i + 2)번째 줄의 (j + 1)번째 수는 좌표 (i, j)에서의 땅의 높이를 나타낸다. 땅의 높이는 256보다 작거나 같은 자연수 또는 0이다.

---

예제 입력 1

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

---

예제 출력 1

1 64

---

인벤토리에 블록이 하나 있기 때문에, 맨 오른쪽 아래에 블록을 하나 채우면 된다.

---

코드

import sys

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

lo = min([min(x) for x in land])
hi = max([max(x) for x in land])
INF = int(1e9)

def check(land, lv, b):
  # lv 걸리는 시간 -> return -> 불가능시에는 아주 큰 값
  sc = 0
  # 채워넣어야할 블록
  c = 0
  for i in range(n):
    for j in range(m):
      z = land[i][j] - lv

      # 현재 칸에서 lv을 뺐을 때 0보다 높을 경우
      if z > 0:
        # 인벤토리에 추가
        b += z
        # 2초 * 개수 
        sc += 2*z
      else:
        # 채워야할 블록 개수 및 시간(1초라서)
        c += -z
  if b < c:
    return INF
  return sc + c
      
msc = INF
mlv = 0

for lv in range(hi, lo-1, -1):
  sc = check(land, lv, b)
  
  # 현재까지의 최소 시간 msc보다 현재 lv의 소요시간인 sc이 작다면 실행
  if msc > sc:
    msc = sc
    mlv = lv
    
print(msc, mlv)

---

풀이

시간 : 900ms - pypy3
메모리 : 117524KB

Class 2의 마지막 문제인만큼 다른 문제들보단 난이도가 있었고, 브루트 포스 알고리즘을 활용했다.

해당 알고리즘의 자세한 설명은 다른 게시물을 참고하면 된다.

1. n, m, b을 입력받고, N*M개의 땅의 높이를 입력받아 land에 저장
2. 탐색할 범위인 가장 낮은 땅의 높이 lo, 가장 높은 땅의 높이 hi를 설정
3. 그 후 현재 설정한 땅의 높이 lv를 기준으로 땅을 평평하게 만들 수 있는지 확인하는 check 함수를 작성
4. 만약 land[i][j]에서 lv를 뺀 값을 저장한 z가
   • 0보다 큰 경우 : 인벤토리 b에 추가하고, 2초 추가
   • 0보다 작은 경우 : 채워야할 블록 개수 c에 추가(1개당 1초이므로 시간도 동일)
5. 만약 c가 b보다
   • 큰 경우 : 채워야할 블록의 개수가 가지고 있는 블록의 개수보다 많다는 것을 의미하므로, 불가능하다는 뜻으로 INF를 return
   • 작은 경우 : 땅을 평평하게 만들 수 있다는 것을 의미하므로, 1번 작업을 의미하는 sc와 2번 작업을 의미하는 c를 더해서 return
6. for문을 hi부터 lo까지 내림차순으로 적용해 답이 여러 개 있다면 그 중에서 땅의 높이가 가장 높은 것으로 출력
7. sc에 check 함수를 호출해 소요 시간을 return받아 저장
8. 그 후 sc가 msc(lv 전까지 lv의 최소시간)보다 시간이 적게 걸릴 경우에만 msc와 mlv 변경 해 저장
9. 그 후 msc와 mlv 출력