[BOJ] 18111 마인크래프트

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

코드 1 - 실패

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

field = []

minh = 257
maxh = -1
for i in range(n):
  field.append(list(map(int, input().split())))
  minh = min([minh,min(field[i])])
  maxh = max([maxh, max(field[i])])

ans = []
for h in range(minh, maxh+1):
  rest = b
  time = 0
  minus = False
  for i in range(n):
    for j in range(m):
      dif = field[i][j] - h
      if dif > 0:
        rest += dif
        time += 2 * dif
      elif dif < 0:
        rest += dif
        if rest < 0:
          minus = True
          break
        time -= dif
    if minus:
      break
  if not minus:
    ans.append((time, h))

ans.sort()

mintime = ans[0][0]
maxh = 0

for i in ans:
  if i[0] == mintime:
    maxh = max([maxh, i[1]])

print(mintime, maxh)

3중 for문 돌리는 것으로 최소 높이에서 최대 높이까지 일일이 다니며 시간을 구하고 최소 시간과 높이를 구하는 방식을 가장 먼저 생각했다. 그렇게 해도 높이 최대 257, 가로, 세로 각 500씩 해서 대충 64,250,000번 연산하는 걸로 나와서 시간 제한 1초컷 할 수 있을 줄 알았는데 시간 초과로 실패했다.

코드 2

생각해보니 그냥 블록 높이별 개수만 알면 높이 차 구하는거랑 공사하는 시간 계산하는건 쉬우니까 해시처럼 해보면 어떨까 싶었다.
n, m, b = map(int, input().split())

field = [0] * 257

for i in range(n):
  for i in list(map(int, input().split())):
    field[i] += 1

minh = -1
for i in range(257):
  if field[i] != 0:
    minh = i
    break

maxh = -1
for i in range(256, -1, -1):
  if field[i] != 0:
    maxh = i
    break

ans = []
for h in range(minh, maxh+1):
  rest = b
  time = 0
  minus = False
  for i in range(minh, maxh+1):
    if field[i] == 0:
      continue
    dif = i - h
    if dif > 0:
      rest += dif * field[i]
      time += 2 * dif * field[i]
    elif dif < 0:
      rest += dif * field[i]
      if rest < 0:
        minus = True
        break
      time -= dif * field[i]
  if minus:
    continue
  ans.append((time, h))

ans.sort()

mintime = ans[0][0]

for i in range(len(ans)-1, -1, -1):
  if ans[i][0] == mintime:
    print(mintime, ans[i][1])
    break

그렇게 했는데 시간초과는 안 나는데 1%에서 틀렸다고 나온다. 예시는 다 통과하는데......
계산하는 중간에 인벤토리의 수가 음수가 되자마자 중단했던 것이 원인이었다. 다음 높이의 작업에서 블록이 남아서 메울 수 있는 경우를 생각을 안 했다.

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

field = [0] * 257

for i in range(n):
  for i in list(map(int, input().split())):
    field[i] += 1

minh = -1
for i in range(257):
  if field[i] != 0:
    minh = i
    break

maxh = -1
for i in range(256, -1, -1):
  if field[i] != 0:
    maxh = i
    break

ans = []
for h in range(minh, maxh+1):
  rest = b
  time = 0
  for i in range(minh, maxh+1):
    if field[i] == 0:
      continue
    dif = i - h
    if dif > 0:
      rest += dif * field[i]
      time += 2 * dif * field[i]
    elif dif < 0:
      rest += dif * field[i]
      time -= dif * field[i]
  if rest < 0:
    continue
  ans.append((time, h))

ans.sort()

mintime = ans[0][0]

for i in range(len(ans)-1, -1, -1):
  if ans[i][0] == mintime:
    print(mintime, ans[i][1])
    break

한 턴이 끝나고 나서 남은 블록수를 확인하게 바꿨더니 통과했다.