[백준] 커플 만들기(1727)

문제 링크 : [백준] 커플 만들기(1727)

문제 설명

두 1차원 배열이 주어졌을 때, 원소의 갯수가 작은 배열의 모든 원소들을 원소의 갯수가 큰 배열과 1:1 쌍을 이룰 때, 쌍을 이룬 값들의 차이의 합이 최소가 되는 값을 구하여라.

입력

n(첫번째 배열의 원소 갯수, 1<=n<=1,000)
m(두번째 배열의 원소 갯수, 1<=m<=1,000)
Di(첫번째 배열의 원소들, 1<=Di<=1,000,000)
Ei(두번째 배열의 원소들, 1<=Ei<=1,000,000)

2 1
10 20
15

출력

5

카테고리

#DP, #정렬

시간 복잡도 상한

O(N² * logn) 까지 가능합니다.

해결 방법

1. 최대한 많은 쌍을 구해야하기 때문에, 원소의 갯수가 작은 배열(As을 기준으로 다른 배열로 모든 원소들의 쌍을 구해주면 됩니다.
2. 두 배열을 오름차순으로 정렬 했을 때, A배열의 원소 Ai, Ai+k과 B배열의 원소 Bj, Bj+l이 있다고 할 때(k,l>0),
   2-1. Ai+k=Ai+Va
   2-2. Bj+l=Bj+Vb
   2-3. Ai-Bj=T
   2-3. 위 처럼 정의하고, Ai과 Bj+l, Ai+k과 Bj이 짝을 이룬다고 하면, 두 쌍의 차이의 합은
   |Ai-Bj+l|+|Ai+k-Bj| = |Ai-Bj-Vb|+|Ai-Bj+Va|=|T-Vb|+|T+Va| -> (1)
   2-4. Ai과 Bj, Ai+k과 Bj+l이 짝을 이룬다고 하면, 두 쌍의 차이의 합은
   |Ai-Bj|+|Ai+k-Bj+l| = |Ai-Bj|+|Ai+Va-Bj-Vb|=|T|+|T+Va-Vb| -> (2)
   2-5. (1)과 (2)의 대소비교를 위하여, 각 절대값들의 제곱을 구합니다.
   1) (1) -> (T-Vb)2+(T+Va)2 = 2T2+2TVa-2TVb+Va2+Vb2
   2) (2) -> T2+(T+Va-Vb)=2T2+2TVa-2TVb+Va2+Vb2-2VaVb
   3) 양 변에서 공통 부분을 제거하고 식을 정리하면,
   (1)-2VaVb=(2)이 됩니다.
   4. 두 배열은 오름차순으로 정렬 되어 있기 때문에, Va, Vb는 항상 0보다 같거나 큽니다.
   5. 즉 (1)>=(2) 식이 항상 성립합니다.
3. 2의 정리들을 활용하여, 오름차순으로 정렬 된 배열들을, 기준 배열에서 다른 배열로 짝을 이룰 때, 인덱스가 역순으로 이어지는 경우는 제외할 수 있습니다.
4. 아직 경우의 수가 많지만, 기준 배열의 한 인덱스가 타겟의 한 인덱스를 선택하거나 하지 않는 경우, 두 경우에 대해 sub problem으로 문제가 제정의 될 수 있으므로, DP를 활용하여 문제에 접근 할 수 있습니다.

시간복잡도

O(nlogn)+O(mlonm)+O(n*m)

코드

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long l;
int n,m,d[1000],e[1000],i,j,v[1000][1000];
l f[1000][1000];
l a(l x){return x>0?x:-x;}
l b(l a,l c){return a>c?c:a;}
l r(int* a1,int* a2,int x,int y){
    if(!x)return 0;
    if(!y)return 1000000000000;
    x--;y--;
    if(v[x][y])return f[x][y];
    f[x][y]=a(a1[x]-a2[y])+r(a1,a2,x,y);
    f[x][y]=b(f[x][y],r(a1,a2,x+1,y));
    v[x][y]=1;
    return f[x][y];
}
int main(){
    scanf("%d%d",&n,&m);
    for(i=0;i<n;i++)scanf("%d",d+i);
    for(i=0;i<m;i++)scanf("%d",e+i);
    sort(d,d+n);sort(e,e+m);
    printf("%lld",n<m?r(d,e,n,m):r(e,d,m,n));
}