백준 18111번 바로가기

나의 풀이

# 입력
n, m, b = map(int, input().split())
blocks = []
for _ in range(n):
  for i in map(int, input().split()):
    blocks.append(i)
    
from collections import Counter
blocks=Counter(blocks)
time = 1000000000
current = 0

# 처리
for h in range(257):
  temp = 0
  a = b
  for i in blocks.keys():
    dif = h-i
    if dif >= 0:
      temp += dif * blocks[i]
      a -= dif * blocks[i]
    else:
      temp -= dif * blocks[i] * 2
      a -= dif * blocks[i]
  if a >= 0:
    if time >= temp:
      time = temp
      current = h

print(time, current)

CODE REVIEW

  1. 브루트포스로 풀어내는 문제. 조건에 맞게 for문을 작성하는게 은근 까다로워 푸는데 시간이 오래 걸렸다.
  2. python3이라 그런지 시간 초과 에러가 발생해서 collections라이브러리의 Counter를 이용해서 풀어냈다. 모든 땅을 각각 저장하는 대신 땅의 높이에 따라 정리하니까 시간 복잡도가 O(n*m)에서 O(256)으로 줄어들었다.
  3. 반례 모음으로 충분히 테스트 해본 뒤에 결과를 제출하자. 생각지도 못한 반례가 은근 있어서 놀랬다.