죄송합니다만, 저는 아직 제 풀이가 완벽한 해법이라고 장담하지 못한다는 점을 미리 밝힙니다.
(틀린답이 나오지는 않겠지만 최악의 경우에 대한 시간복잡도를 잘 모르겠습니다)
제가 원래 "일단 해보자" (잘못됐다는건 알지만 고치기 힘든) 는 마인드를 갖고 있어서,
혹시나 하는 마음으로 해봤는데 시간내에 나와주네요.


문제는 굉장히 간단합니다.
주어진 두개의 set, S와 T에 속하는 원소를 각각 s와 t라고 할때,
이들을 서로 pair로 만들어서 cost를 가장 작게 하는건데요,
cost는 모든 pair의 abs(s-t) 의 합이며, S와 T의 모든 원소가 pair에 속해야 합니다.


 

N 제한 50,000을 생각하지 않고 떠오르는 가장 간단한 방법은 Dynamic Programming입니다.

A[i][j] = set S 의 i번째 원소까지, set T의 j번째 원소까지 match시켰을때 최소 cost의 합 이라고 정의하면

A[i][j] = min (A[i-1][j-1], A[i-1][j], A[i][j-1]) + abs(S[i] – T[j]);

가 되겠습니다. 이는 S와 T가 increasing order로 들어온다는 조건이 있기 때문에 가능하죠.
하지만 이 방법은 시간복잡도가 O(N^2) 이 되겠습니다. 막막하죠.

 


제 풀이법은 이 DP의 시간복잡도를 약간 개선시킨 것입니다.
set S 의 모든 원소들에 대해서 set T의 모든 원소를 보지 않고, “가능성이 있는 원소” 들만 고려하였습니다.

예를 들어보겠습니다.

입력으로 S = {4, 5, 7, 9}, T = {1, 3, 20, 30} 가 주어졌습니다.

여기서 S의 5는 “절대” T의 1과 match되지 않습니다. 왜냐하면,

abs(4-1) + abs(5-1) = 3 + 4 = 7,

abs(4-1) + abs(5-3) = 3 + 2 = 5 이기 때문입니다.
즉, (4,1), (5,3) pair로 만들었을때 cost가 5인데, 그보다 더 cost가 큰 (4,1) (5,1) pair를 만들 필요가 없다는 말이죠.
만약에 T의 두번째 원소가 3이 아니라 10이었다면, 5는 1과 pair가 될 수도 있을 것입니다.

 

아시겠나요?



그럼 이제 간략한 소스코드 설명 들어가겠습니다.


 

define은 다음과 같이 되어있습니다.



아래의 소스코드는 모든 S의 i번째 원소에 대하여 그 원소와 “pair가 될 수 있는” 원소들의 범위를 구하는 것입니다.

a[i]는 set S의 i번째 원소이며, b[i]는 set T의 i번째 원소 입니다.

n1은 set S의 원소 갯수이며, n2는 set T의 원소 갯수 입니다.

c[i][0]은 set S의 i번째 원소와 pair가 될 수 있는 set T의 원소들 가운데 lower bound의 index를 가리키며,

c[i][1]은 set S의 i번째 원소와 pair가 될 수 있는 set T의 원소들 가운데 upper bound의 index를 가리킵니다.

여기까지의 시간복잡도는 겉보기와 달리 실제로 따져보면 O(N)이 되겠습니다.




그리고 나서 DP를 돌리는 과정은 다음과 같습니다.


무식하게 생각하면 DP를 구현하기 위해서 O(N^2)의 공간이 필요하지만 아주 조금만 생각하면 O(N)짜리 배열 두개만이 필요하다는 것을 알 수 있을 것입니다. d[0]과 d[1]이 그 두개의 dynamic table이 되겠습니다.

제 해법이 완벽하지 않다고 글의 서두에 밝힌 이유는 바로 이 부분에 대한 시간복잡도를 제대로 구할 수 없었기 때문입니다.

 

이상으로 웬지 허무한 J번 editorial 이었습니다.

 

 


과연 이 알고리즘이 정확한 해법일까요??

 

이 게시물을..