[1727] 커플 만들기

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

1727번: 커플 만들기

점화식은 매우 간단한데, 정렬하고 dp를 돌린다는 발상이 쉽게 떠오르지 않는다.

현재 (i, j)를 매칭하는 경우 / i를 스킵하는 경우 / j를 스킵하는 경우, 총 3가지로 분기해도 되지만,

n<m을 만족하도록 입력을 swap해두면 (i, j)를 매칭하는 경우와 j를 스킵하는 경우. 총 2가지로만 분기할 수 있다.

---

#include <bits/stdc++.h>

using namespace std;

#ifdef ONLINE_JUDGE

constexpr bool local = false;

#else

constexpr bool local = true;

#endif

using ll = long long;

using pi = pair<ll, ll>;

constexpr int INF = (int)1e9;

int n, m, S, dp[1005][1005];

vector<int> a, b;

int f(int i, int j, int d) {

    if (i < 0 || j < 0) return ((d == S) ? 0 : INF);

    if (dp[i][j] != -1) return dp[i][j];

    dp[i][j] = min(f(i - 1, j - 1, d + 1) + abs(a[i] - b[j]), f(i, j - 1, d));

    return dp[i][j];

}

int main(void) {

    if (!local) ios_base::sync_with_stdio(0), cin.tie(0);

    int i;

    cin >> n >> m;

    S = min(n, m);

    a.resize(n);

    b.resize(m);

    for (i = 0; i < n; i++) cin >> a[i];

    for (i = 0; i < m; i++) cin >> b[i];

    sort(a.begin(), a.end());

    sort(b.begin(), b.end());

    memset(dp, -1, sizeof(dp));

    if (n > m) swap(a, b), swap(n, m);

    cout << f(n - 1, m - 1, 0);

    return 0;

}

---