• 책 361p
• 백준 18310번: 안테나

문제

풀이

처음 든 생각

• 브루트포스

  • 설치할 수있는 모든 경우마다, 모든 집까지의 거리를 계산해본다.
  • 집의수가 N일때 N개마다 N-1 번씩 거리를 계산해야하므로
    O(N^2) 번 연산해야한다. 또 이걸 정렬하는데, O(NlogN)만큼 걸리지만, 일단 N^2가 가장 크니까 무시하자.
  • N=최대 200,000 이므로 40,000,000,000 시간 제한 1초를 훌쩍 넘는다. 안되겠구만,,

• 경우 가지치기

  • 어쨌던간에 가장 적은 거리의 총합을 만드는 위치는 첫번째집과 마지막 집 사이에 있을 것이다.
  • 이 명제는 계속계속 안으로 파고들어도(1~n번째집 -> 2~n-1번째집 -> 3~n-2번째 집) 성립할 것 같다 아마도,,
  • 선형선에서의 상대적 위치의 총합은 절댓값이다. 이 절댓값이 가장 작을때는 상대적 위치의 합이 제일 적다는 것이고, 절댓값이 가장 작은 경우는 0이고, 이게 우리가 원하는 상황인거고, 그러면 피봇이 제일 0에 가깝(=가장 중간일때)울때가 가장 절댓값이 작음을 보장할것이다. 아마도!
  • 그러다보면 안테나는 집이 위치한 곳에만 설치할 수 있으니까,, 가장 중간에 있는 집에 안테나를 설치하면 되겠구만.

풀이아이디어

아싸 내가 생각한게 맞았삼

정확히 중간값에 해당하는 위치가, 모든 집 까지의 거리의 총합이 최소가 된다

코드

n = int(input())
data = list(map(int, input().split()))
data.sort()
print(data[(n-1)//2]) # 중간값 출력

느낀점

대충 "이렇게 되면 저걸 보장하지 않나?!" 가 좀 명확했음 좋겠다.
오늘은 좀 럭키였지만 이래저래~되겠구만~~ 머릿속으로 그리고 넘어가지 말고 기호로 나타나서(하다못해 블로그에 왜 그렇게 생각한건지 명문화라도 하자!) 제대로 증명할 수 있음 증명하고 넘어가는 습관을 들이자 (+시간복잡도도!)