https://www.acmicpc.net/problem/23090
요약
- 좌표가 주어질때마다 적절한 점을 골라 거리가(맨하탄거리) 최소인 점 + 그 때의 거리 구하기
- 최소인 점은 x=0 위에 있고
- 연속으로 주어지는 좌표마다 처리를 해야함
- 공식 풀이
접근법
- x 좌표는 결정에 영향을 미치지 않음. 거리의 합에만 이용함
- y끼리 모여있을때 적절한 점을 구해야 하는데..
- 이런류의 문제는 어디선가 풀어보았음
- 앞에서부터 처리하다가 감소했다가 증가하고..(아래로 볼록 그래프)
- 삼분 탐색으로 처리하거나
- 읽어가다가 변화량이 증가하는 곳을 찾거나
- 숫자 3개로 이리저리 엑셀로 그래프를 그려보니 가운데 있는 점이 최소가 되었음
- 더 생각해보니 다음과 같았음
- 각 점마다 그래프가 꺾일 것임 => 후보가 되는 점은 꺾이는 점중에 하나 => y 점들
- 그래프의 모양은 각각의 구간별로 다를텐데 대략 이런 모양일 것임
- 절대값 처리 : a−x 이거나 x−a
- a−100x,b−98x,.....c−2x,2x+d,...z+100x
- 기울기가 -100, -98, .... 감소하다가
- 어느순간 2, 4, .... 증가할 것임
- 그리고 아래로 볼록 그래프니까 감소하다가 증가하는 어딘가가 "중간"
- 입력되는 값들의 "중간값"을 처리하는 문제임