BOJ 1866 택배, 2141 우체국을 풀면서...

택배 문제를 보면 헬기로 여러개를 한 번에 운송할 때 어디로 운송하는 것이 가장 효율적인지를 고민해야 하는데, 이것을 식(그래프)으로 나타내면 다음과 같다.

y=|x-k1|+|x-k2|+|x-k3|+...+|x-kn|
y는 우리가 구하고자 하는 최소비용이고, x는 최소 비용을 만들기 위해 운송해야할 위치를 나타낸다. 즉 위치x로 운송했을 때 최소 비용이 나와야한다. k는 각 물건들의 목적지이고, 오름차순으로 배열된 상태이다.**

이 경우는 쉬운 편이다. 그래프를 그려보면 항상 k값들의 중간값에서 기울기가 음과 양으로 갈린다. k값들의 중간 값을 기준으로 왼쪽은 음의 기울기 오른쪽은 양의 기울기를 가지는 그래프가 된다.
생각해보면 당연하다. 이 절대값 기호로 둘러싸인 식을 일반식으로 풀어낸다고 생각해보자.
절대값 기호 안의 값이 양수이면 그냥 그대로, 음수이면 식에 -를 붙여준다. 지금 k값들이 크기순으로, 오름차순으로 배열되어있기 때문에, x가 가운데 값일 때, 그 가운데 값을 기준으로 왼쪽은 절대값 기호 안의 식이 양수가 되고, 오른쪽 식들은 음수가 되어버린다.

그래서 가운데 값을 기준으로 x가 가운데 값보다 작을 때는 -x값들이 더 많아지는 것이므로 기울기가 음수가 되고, 그 반대는 기울기가 양수가 되는 것이다.

그렇기 때문에 결국 x를 가운데 값으로 설정했을 때 최소값을 가지게 되는 것이다. 그리고 k값들의 개수가 짝수인 경우는 x가 될 수 있는 값이 가운데 2개가 같은 최소값을 갖게 될 것이고 아무거나 선택해도 된다.

2141번 우체국 문제 같은 경우는 약간 더 생각을 해봐야한다.
식(그래프)이 y=a1*|x-k1|+a2*|x-k2|...an*|x-kn| 이런식으로 절대값 기호 앞에 곱이 하나 붙는다. 이렇게 되면, 일반식으로 풀어썼을 때 x앞에 계수가 붙으므로 이 계수의 크기가 중요해진다. 그래서 결국 선택을 할 때 계수값들의 합의 중간값이 포함된 k를 선택해줘야 하는 것 같다.
center=(a1+a2+...+an)/2 라고 하면 center값이 포함되는 부분의 k값을 x의 값으로 해야 그래프에서 최소값이 나오는 부분이 되는 것 같다.
결국 2141을 AC받았는데, 틀렸던 이유는 sort를 안해준 것이었다.

2141 우체국 문제를 다시 풀었는데, 예전에 풀었던 것을 보니 누적합을 따로 구해놓고 비교했던데, 그럴 필요 없이 맨 처음에 전체 합(sum)을 구해놓고, sorting한 후, for문 돌면서 처음부터 누적합(psum)을 구하면서 psum>=sum-psum 이 되는 순간 그에 해당하는 x좌표가 답이된다. 처음으로 psum>=sum-psum 이 되는 순간이 바로 그래프에서 기울기가 0이 되기 시작하거나, 음의 기울기에서 양의 기울기로 바뀌는 순간이기 때문이다. 그래서 그 부분이 최소값!