cubelover의 블로그

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


정수로 이루어진 두 집합 S와 T가 있다. S와 T 간에 원소를 연결해서 S의 각 원소가 적어도 하나의 T의 원소와 연결되고, T의 각 원소가 적어도 하나의 S의 원소와 연결되어야 한다. a와 b를 연결할 때의 비용은 |a-b|이고, 전체 비용의 합을 최소화시키는 것이 목적이다.


앞으로 적어도 하나의 다른 원소와 연결되는 것을 '연결 조건을 만족한다'고 하자.


소정리 1. 만약 a와 b를 연결하고 c와 d를 연결하는 최적해가 존재하고 a<c이며 b>d라면, a와 d를 연결하고 b와 c를 연결하는 최적해가 존재한다.


이는 두 쌍의 연결 방법을 바꿈으로써 다른 원소가 영향받지 않고, 비용이 증가하지 않음에서 쉽게 알 수 있다.


이 정리 하나만으로 쉽게 O(nm) 풀이를 만들 수 있다. D[i][j] = (S에서 오름차순으로 i개, T에서 오름차순으로 j개가 연결 조건을 만족할 때 최소 비용)으로 정의하면, 다음과 같은 점화식을 통해 계산이 가능하다.


D[i][j] = min { D[i-1][j-1], D[i-1][j], D[i][j-1] } + |S[i]-T[j]|


그러나 이 방법으로는 제한이 500,000이기 때문에 쉽게 시간 초과가 발생한다.


최적해가 가지는 다른 특징을 찾아보기 위해 예제를 다음과 같이 그림으로 나타내 보았다.



여기서 우리는 다음과 같은 소정리를 하나 얻는다.


소정리 2. S의 원소 a<c와 T의 원소 b<d가 있을 때 a와 b를 연결하고 c와 d를 연결하는 최적해가 존재한다면, a와 d를 연결하거나 b와 c를 연결하지 않는 최적해가 존재한다.


이게 무슨 소리인지를 그림으로 나타내면 아래와 같다.



즉, 그림처럼 a와 b, c와 d가 연결되어 있다면 여기서 a와 d를 연결하거나 b와 c를 연결하는 것은 이득이 되지 않는다는 것이다. 당연한 소정리지만 덕분에 우리는 모든 연결을 두 종류로 나눌 수 있다.



빨간색 실선을 강한 연결, 회색 화살표를 약한 연결이라고 하자. 강한 연결은 S와 T에서 하나씩 선택해 연결한 것이며, 약한 연결은 S 또는 T의 원소를 가장 가까운 다른 원소에 연결한 것이다. 이로부터 O(n+m) 풀이를 이끌어낸다.


S와 T의 원소들을 통째로 오름차순으로 정렬하고, D[i] = (i번째 원소까지 연결 조건을 만족했을 때 최소 비용)이라고 정의하자. 그러면 두 가지 경우가 생김을 알 수 있다.


첫 번째 경우는 i번째 원소가 약한 연결로 연결될 때이다. 이 경우는 i번째 원소에서 가장 가까운 다른 원소를 연결한다.


두 번째 경우는 어떤 j에 대하여 j+1~i번째 원소가 모두 강한 연결로 일대일 대응될 때이다. 이 경우 j+1~i번째 원소 중 S에 속하는 원소의 개수와 T에 속하는 원소의 개수가 같아야 한다. 그런 j가 여러 개일 수 있는데, 이 때 가장 큰 j만 고려해도 충분함을 알 수 있다. 만약 더 작은 j'에 대해서 j'+1~i까지 모두 일대일 대응시키는 것이 최적해라면, 이는 D[j]를 계산할 때 j'+1~j까지 일대일 대응시키는 경우가 포함되어 있고, D[i]를 계산할 때 j+1~i까지 일대일 대응시키는 경우가 포함되어 있으므로 가장 큰 j만 고려해도 충분하다.


첫 번째 경우는 O(1)에 처리할 수 있지만, 두 번째 경우는 다소 어려워 보인다. 우리가 고려하는 j가 j+1~i번째 원소 중 S에 속하는 원소의 개수와 T에 속하는 원소의 개수가 같은 최대의 j이므로, j+1~i-1에서는 항상 S에 속하는 원소의 개수가 T에 속하는 원소의 개수보다 많거나, 아니면 그 반대이다. 따라서 j+1~i번째 원소를 일대일 대응하는 최소 비용은 |(S에 속하는 원소들의 합)-(T에 속하는 원소들의 합)|이 되므로, 이 또한 O(1)에 처리할 수 있다.


입력으로 S와 T의 원소가 오름차순으로 주어지므로 이를 병합하면서 위 과정을 수행하면 O(n+m)에 해결이 가능하다.

신고

'...' 카테고리의 다른 글

Baekjoon Online Judge 13538  (3) 2016.11.03
Baekjoon Online Judge 1659  (0) 2016.02.02
1 이상 N 이하의 정수에서 i의 빈도수  (0) 2016.01.27

Comment +0