1727 - 커플 만들기

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

비교하고자 하는 배열 $a$의 크기는 항상 배열 $b$보다 작다.
배열 $a$로부터 차이를 최소로 하는 배열 $\{ b_i, b_{i+1}, \dots, b_j \}$ $(0 \le i \le j \le n)$ 을 찾는다.

스위핑으로 되려나싶어서 코드를 다음과 같이 작성해봤다.

int ptr = -1, sum = 0;
for(int i=0; i<n; ++i){
    int val = INF;
    for(int j=ptr+1; j<=m-(n-i); ++j){
        if(val > abs(a[i]-b[j])){
            val = abs(a[i]-b[j]);
            ptr = j;
        }
    }
    sum += val;
}
return sum;

그러나 아래와 같이 이전에 작은 손해가 있지만 결과적으로 최소가 나오는 케이스에서 오답을 출력했다.

3 6
10 20 30
9 10 11 100 101 102

A = [10, 20, 30]
B = [ 9, 10, 11]

이여야하는데, 원소가 하나씩 밀려서 B = [10, 11, 100] 가 되버린 것이다.

이거 DP구나 깨닫고 $O(|A||B|)$ 를 다 해보자 싶었다.

int solve(int apos, int bpos){
    if(apos == n) return 0;
    
    int& r = dp[apos][bpos];
    if(r != -1) return r;
    
    r = INF;
    for(int i=bpos; i<=m-(n-apos); ++i){
        r = min(r, abs(a[apos]-b[i]) + solve(apos+1, i+1));
    }
    return r;
}

범위를 $|B|$ 배열 길이만큼이 아닌, 남은 $|A|$의 길이만큼으로 했지만 역시 느렸다. 속도가 빠른 소스들을 보니 이렇게 해결한 것 같다.

$min( b[bpos]$를 선택하는 경우, 선택하지 않고 $b[bpos+1]$과 $a[pos]$를 매칭하는 경우 $)$

재귀가 2번씩만 호출되니까 엄청 빨라졌다.

#include <bits/stdc++.h>
using namespace std;

#define INF 987654321

typedef long long lld;

int n, m;
vector<int> a, b;
int dp[1001][1001];

int solve(int apos, int bpos){
    if(apos == n) return 0;
    if(bpos == m) return INF;
    
    int& r = dp[apos][bpos];
    if(r != -1) return r;
    
    // bpos를 선택한다
    r = abs(a[apos]-b[bpos]) + solve(apos+1, bpos+1);
    // 안 한다 (다음으로 미룬다)
    r = min(r, solve(apos, bpos+1));
    return r;
}

int main(){
    memset(dp, -1, sizeof(dp));
    scanf("%d %d", &n, &m);
    a.resize(n);
    b.resize(m);
    for(int i=0; i<n; ++i) scanf("%d", &a[i]);
    for(int i=0; i<m; ++i) scanf("%d", &b[i]);
    
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());
    
    if(n > m){
        // a(n)이 항상 작은 배열
        swap(a, b);
        swap(n, m);
    }
    
    printf("%d", solve(0, 0));
    
    return 0;
}