이 문제는 데이터 사이즈가 작아 가능한 모든 지점에서 직접 계산하여 답을 구하여도 되나 데이터 사이즈가 크지는 경우 수학적인 방법으로 답을 구할 수 있습니다.

hint

a1< a2 < a3 < ... < an

f(x) = |x-a1| + |x-a2] + |x-a3| + .. |x-an| 일 때 f(a_n/2)일 때 최소값이다.

예를 들어 ,

• f(x) = |x-1| + |x-5| + |x-6| 이면 f(5) 가 최소값이고
• f(x) = |x-1| + |x-5| + |x-7| + |x-8| 이면 f(5) 혹은 f(7) 에서 최소값 입니다.

그래프로 해석

홀수 개 일 때 예들 보면

f(x) = |x-1| + |x-5| + |x-6|

절대 값 안을 0 으로 만드는 세 값을 기준으로 네 가지 다른 상태가 만들어 집니다. 즉 x= 1,5,6

1. x 가 1 보다 작은 영역에서는 세 절대 값안이 음수 이므로 - 를 붙여서 절대 값을 빠져 나오니 f(x)의 기울기는 -3 이 됩니다.
2. 1 과 5 사이에서는 하나는 양수로 두 개는 음수로 빠져 나옵니다. 즉 하나의 x 는 서로 상쇄되어 기울기는 -1 이 됩니다. 즉 전 상태에서 보다 기울기(절대값)는 줄어듭니다. 여기까지가 f(x) 의 기울기가 음수가 되는 영역이고
3. 마찬가지로 5 와 6 사이에서는 f(x) 의 기울기는 1 이고
4. 6 이상에서는 기울기는 3 이 됩니다.

그래서 그래프의 개형은 아래 그림과 같이 됩니다.

즉 이런 유형의 그래프는 중간 지점에서 연필 촉 같은 모양의 그래프가 만들어 지고 이 때가 최소 값이 됩니다.

---

짝수 개일 때의 예를 보면

f(x) = |x-1| + |x-5| + |x-7| + |x-8|

절대 값을 0 으로 만드는 지점이 4 개 입니다. 즉 x = 1 , 5, 7 ,8 이 만들어지고 5 가지 상태가 만들어 집니다.

홀수 개 일 때와 다른 점은 5 와 7 사이 점을 두면 반(이 경우는 두 개)은 음수가 되고 반은(이 경우 두 개)은 양수가 되어 서로 상쇄되어 기울기가 0 이 되어 버립니다.

f(x) = 상수

이 경우의 그래프는

가 되어 5 와 7 사이에서 최소 값이 나오게 됩니다.