[백준 8987번] 전봇대 (Python3)

def cal(x):
  if not memo.get(x):
    memo[x] = sum([abs(i*x-data[i]) for i in range(N)])
  return memo[x]
  
N = int(input())
data = [*map(int,input().split())]

memo = {}
last = memo[0] = sum(data)

x,c = 1,0
while c >= 0:
  if cal(x) < last and cal(x) < cal(x-1):
    last = cal(x)
    x += 2**c
    c += 1
  else:
    last = cal(x-2**c)
    x -= 2**(c-1)
    c -= 2

print(min(memo.values()))

구현은 간단하지만 아이디어를 떠올리기 굉장히 어려웠다.

기본적으로 이분탐색을 사용하는 문제라는건 떠올릴 수 있었다. 전봇대 이동에 필요한 비용이 최솟값(구하고자하는 값)을 기준으로 간격에 대해 증가하는 함수 꼴을 그리기 때문이다. (한마디로 그래프의 형태가 y=x^2 혹은 y=|x| 와 비슷하다)

 

그런데 문제는 이분탐색을 할 때, 최소비용이 어디에 존재하는지를 확인하는 방식을 정하는 것이 필요했다. 이분탐색을 할 때 값이 감소하더라도 최소비용은 현재의 뒤에 존재할 수 있기 때문이다.

그래서 나는 이것을 현재의 비용이 현재보다 1 작을때의 비용보다 큰지를 확인하는 방식으로 구현하였다.

만약 현재보다 1 작을때의 비용이 현재의 비용보다 더 작다면, 최소비용은 현재보다 더 작은 값에 존재한다는 뜻이다. 반대로 현재보다 1 작을때의 비용이 현재보다 더 크다면, 최소비용은 현재보다 더 큰 값에 존재한다는 뜻이다.

 

이를 기준으로 잡고, c (2의 차수) 를 늘리고 줄여가면서 최소비용을 구할 수 있었다.

 

굉장히 까다로운 문제였고 푸는데 오래 걸렸지만 최종적인 코드는 깔끔하게 짜여진 것 같아서 만족스러웠다.

 

 

오늘의 교훈) 이분탐색을 잘 활용하자