[BOJ] 2431 신호장애

www.acmicpc.net/problem/2431

삽질을 많이 해서(그럴만한 문제다) 4시간 정도 때려박아서 풀었다.
문제를 다시 써보면 다음과 같다.

수열 $x_1,x_2,...,x_n$ 이 주어졌을 때 이 중 몇 원소에 -1을 곱하고 오름차순으로 정렬하자.
$y_i=k+(i-1)\cdot \frac{2m}{n}$로 정의할 때 적당한 $k$를 골라 $\left| x_1-y_1 \right| +\left| x_2-y_2\right| +...+\left| x_n - y_n\right|$ 을 최소화시켜라.

수열 $x_i$가 고정되었다면 구하고자 하는 값은 $k$에 대해 아래로 볼록한 형태를 띈다. 따라서 실수라는 점이 다소 불편하지만 이분탐색으로 최소값을 구할 수 있다.
따라서 수열을 고정시키는 방향으로 생각해보자.
좀 생각해봤는데 잘은 모르겠지만 왠지 오름차순으로 정렬한 다음 짝수 인덱스는 -를 붙이고 홀수 인덱스는 +를 붙이는 게 좋을 것 같았다.
그래서 코딩했더니 맞았다. 와!