BOJ 12766 지사 배정 (분할정복 동적계획법 최적화)

https://www.acmicpc.net/problem/12766

12766번: 지사 배정

방향그래프의 정점에 위치한 그래프들을 S개의 그룹으로 묶어, 한 그룹내에서 모든 지사들 사이에서 통신을 할 때, 총 통신비용을 최적화 하는 문제이다.

두 지사 사이의 통신은 항상 본부를 거쳐서 지나가야 한다. 따라서 본부 s에서 지사 u까지의 거리 D[s][u], 그리고 지사 u에서 본부 s까지의 거리를 D[u][s] 라고 하면, 두 지사 u, v의 통신 비용은 D[u][s] + D[s][u] + D[v][s] + D[s][v] 이다.

우선 본부를 시작점으로 하는 모든 지사까지의 최단거리를 구해야 하는데, 다익스트라 알고리즘으로 구할 수 있다. 반대로, 모든 지사를 시작점으로 하고 본부를 종점으로 하는 최단거리를 구해야 하는데, 이는 원본 그래프의 방향을 반대로 조정하고 본부를 시작점으로 보고 다익스트라를 돌리면 구할 수 있다.

 

어떤 그룹에 지사 a, b, c가 포함이 되는 경우를 생각해보자.
이런 경우 이 그룹의 통신비용은 (a, b), (b, c), (c, a) 쌍의 통신비용의 합이 된다.

지사의 관점에서 보면 모든 지사는 자신을 제외한 모든 다른 지사에 송신을 해야하고, 다른 모든 지사로 부터 수신을 해야 한다. 그룹의 사이즈를 sz라고 하면, 각 지사는 sz-1번 송신, sz-1번 수신을 한다. 모든 송수신은 본부와 하게 되므로, 지사 u의 통신비용은 (D[u][s] + D[s][u]) * (sz-1) 이다.

지사 u와 본부 s사이의 통신 비용 C[u]를 C[u] = D[u][s] + D[s][u] 로 정의 하면, 어떤 그룹 G의 통신 비용은 cost(G) = sum(u in G) { C[u] } * (size(G) - 1) 이다.

 

이제 지사들을 적절하게 그룹을 만들어서 총 통신비용을 최적화 해야한다.

어떤 그룹의 통신 비용은, 그룹의 크기와 그 그룹에 속한 지사와 본부사이의 통신 비용의 합의 곱으로 결정된다. 그룹에 속한 지사들 사이의 관계에는 영향을 받지 않는다. 따라서 크기가 큰 그룹에 본부와 통신 비용이 적은 지사들을 포함시키는 것이 이득이다.

본부와 통신비용이 적은 지사들을 큰 그룹으로 묶고, 그 다음으로 통신비용이 적은 지사들을 다음으로 큰 그룹으로 묶는 식으로 하는 전략이 최적의 해를 구하므로, 지사들은 본부와의 통신비용 순으로 정렬할 뒤, 앞에서 부터 그룹에 넣는 경우를 따져보면 된다.

DP[i][j] = 크기가 j번째로 작은 지사를 i번째 그룹에 넣을 때, 통신비용의 최소값으로 정의를 하면, 아래의 점화식을 얻을 수 있다.

DP[i][j] = min (k < j) { DP[i-1][k] + sum(k + 1, j) * (j - k) }

(위 DP식을 얻는 과정이 어려웠다)

sum(a, b)는 a번째 지사에서 부터 j번째 지사까지, 본부와의 통신비용의 합으로 정의한다. sum(a, b)는 구간합을 이용하여 O(1)에 구할 수 있다.

C[k][j] = sum(k + 1, j) * (j - k) 로 정의하면, 위 점화식은 아래와 같이 다시 쓸 수 있다.

DP[i][j] = min (k < j) { DP[i-1][k] + C[k][j] }

C[k][j]가 monge array 성질을 가지기 때문에 (구간합 기반의 함수이면 대체로 성질을 만족한다), 분할정복을 이용한 DP최적화 기법을 적용할 수 있다.

참조: https://ilyoan.tistory.com/entry/BOJ-13261-%ED%83%88%EC%98%A5

BOJ 13261 탈옥 (분할정복 동적계획법 최적화)

탈옥 문제와 DP 점화식이 거의 같다.
탈옥 문제의 경우, 문제를 따라 점화식을 만들면 자연스럽게 위 점화식이 유도가 된다. 반면, 이 문제의 경우 여러 단계를 거치고, 지사와 본부 사이의 거리순으로 지사를 정렬하는 그리디가 최적임을 발견한 후에 점화식을 유도할 수 있기 때문에, 난이도가 훨씬 높게 느껴졌다.