[codeground] 36. 재활용

codeground - Practice - SCPC 2회 본선 - 36. 재활용
문제 : https://www.codeground.org/practice/practiceProblemList

---

vector<int> arr; //arr[i] : i집의 x위치
vector<int> sum; //sum[i] : 1~i 집들의 x위치 합

int d[501][501]; //d[s][k] : s~n 까지의 집이 k개의 수집통에 재활용을 넣는 경우 드는 최소 비용
int go(int s, int k) //d[s][k] 채우는 함수

일단 x좌표에 대해 오름차순 정렬해준다.
이제 d배열을 채워보자.

---

[그림 1]

만약 a~e 집이 1개의 재활용 수집통을 사용한다고 했을 때, 가장 적절한 수집통의 위치는 어디가 될까.
가장 적절한 수집통의 위치를 x라고 했을 때 |x-a| + |x-b| + |x-c| + |x-d| + |x-e| = y 의 식에서 y가 최소가 되는 x값이 가장 적절한 수집통의 위치라고 할 수 있다.
이 때, |x-a| + |x-b| + |x-c| + |x-d| + |x-e| = y 그래프를 그려보면 [그림 1]의 그래프와 같고 이 때, y가 최소인 x 값은 c가 된다. 즉, a, b, c, d, e 중 중앙에 위치한 index가 최적의 수집통 위치가 된다. 집의 개수가 홀수가 되면 y가 최소인 x값은 중앙의 2개가 되므로(ex. a, b ,c, d의 최적 수집통 위치 = b, c) 홀수 짝수개 상관없이 집들의 중앙값 인덱스를 찾는다고 생각하면 된다.

---

a~e 집이 사용할 최적의 재활용 수집통 위치(mid)를 구했다. 그럼 이 때 거리의 합(cost)을 구해보자.
[그림 1]의 식의 x에 mid를 y에 cost를 대입해보자.

int cost = |mid - a| + |mid - b| + |mid - c| + |mid - d| + |mid - e| 
         = (mid-a) + (mid-b) + (mid-c) + (d-mid) + (e-mid) 

이와 같은 식으로 나타낼 수 있다.

여기서 x좌표를 의미하는 a~e를 arr[1]~arr[5]로 바꿔서 살펴보면

int cost = (mid-arr[1]) + (mid-arr[2]) + (mid-arr[3]) + (arr[4]-mid) + (arr[5]-mid)
         = (arr[4]~arr[5]) - (arr[1]~arr[3]) + (3-2) * mid

가 된다.

sum[i] = arr[1] + arr[2] + … + arr[i] 이라고 하자.
mid = arr[3] 과 같으므로 3을 mind라고 했을 때

int cost 
  = (arr[mind+1] ~ arr[5]까지합) - (arr[1] ~ arr[mind]까지 합) + ((mind - 1 + 1) - (5 - mind))* arr[mind]
  = (sum[5] - sum[mind]) - (sum[mind] - sum[1 - 1] + ((mind - 1 + 1) - (5 - mind))*arr[mind]

가 되고 여기서 1~5를 s~e로 바꿔서 일반화 시켜주면 아래와 같은 식을 구할 수 있다.

int cost 
   = (sum[e] - sum[mind]) - (sum[mind] - sum[s - 1] + ((mind - s + 1) - (e - mind)) * arr[mind]

---

위에서 구한 cost를 이용해서 d[s][k]를 구할 수 있다.
d[s][k]는 s부터 e(s, s+1, ... , n) 까지의 집을 하나의 수집통을 이용해서 채우는 비용 + 나머지 집들을 k-1개의 수집통을 이용해서 비우는 최소 비용 (cost + d[e+1][k-1])를 모두 구해보고 최소 값을 저장하면 된다. 이 때 (s, k)가 같은 경우를 몇 번이나 탐색될 수 있으므로 memoization 하기 위해서 d 배열을 사용했다.

1~n까지의 집을 m개의 재활용 수집통을 이용한 경우의 최소값을 구하는 문제이기 때문에 d[1][m]이 정답이 된다.

d배열을 다 채우는데 O(NM)이 소요되고 해당 배열을 채울 때 최선의 e를 찾기위해 O(N)이 소요되므로 시간복잡도는 O(N^2 * M)가 된다.

---

소스 코드 : https://gist.github.com/fpdjsns/8d805be50c7bb7238b15eeac1943d17e

재활용 (codeground) : https://www.codeground.org/practice

---

백준 택배(1866) 문제를 풀 때가 생각났다. 한 번 풀어보면 좋을 듯 하다.
처음에는 d 배열을 3차원으로 만들어서 d[s][e][k] = s~e집이 k개의 수집통에 재활용을 넣는 경우 드는 최소 비용을 저장해서 구현했는데 메모리 초과가 떴다. 그 후 go함수를 다시 보니 끝나는 지점 e가 모두 N으로 동일하고 변하지 않아서 필요없다는 것을 깨닫고 d[s][k] 2차원 배열을 만들고 go 함수도 끝나는 지점 e 매개변수를 없애서 메모리 초과 문제를 해결했다.

|x-a| + |x-b| + |x-c| + |x-d| + |x-e| = y 그래프 참고 : http://j1w2k3.tistory.com/473