문제

여자친구가 없는 남자 n명과 남자친구가 없는 여자 m명을 불러 모아서 이성 친구를 만들어 주기로 하였다. 하지만 아무렇게나 해줄 수는 없고, 최대한 비슷한 성격의 사람들을 짝 지어 주기로 하였다. 당신은 뭔가 알 수 없는 방법으로 각 사람의 성격을 수치화 하는데 성공하였다. 따라서 각 사람의 성격은 어떤 정수로 표현된다. 이와 같은 성격의 수치가 주어졌을 때, 우선 최대한 많은 커플을 만들고, 각 커플을 이루는 두 사람의 성격의 차이의 합이 최소가 되도록 하려 한다. 남자-여자 커플만 허용된다.

접근

Greedy와 DP 기법을 혼합해 풀었다.

Greedy

남자와 여자의 성격 수치를 저장한 male과 female에 대하여 각각의 원소를 일대일로 짝지어 줄 때, 두 배열을 오름차순으로 정렬하여 계산하면 최적해를 얻을 수 있다. 만약 n과 m이 같다면, 순서대로 짝짓는것이 차이의 합을 최소화하는 방법이다. n과 m이 다르다면, 원소의 개수가 많은 배열에서 적절하게 다른 배열의 원소 개수만큼 원소를 뽑아 순서대로 대응시키는 것이 최적의 방법이다. 이때, ‘절적하게’ 뽑아 개수를 맞추는 것이 문제인데 dp를 이용해 해결하였다.

DP(Dynamic Programming)

male배열과 female배열의 각각 i번째 그리고 l번째 원소부터 고려하는 경우를 생각해보자. 이는 총 두가지 경우로 분열된다.

• male[i]와 female[l]을 대응시키고, male[i+1]과 female[l+1]을 비교하는 경우.
• female[l]을 건너뛰고 male[i]와 female[l+1]부터 고려하는 경우 혹은 male[i]을 건너뛰고 male[i+1]와 female[l]부터 고려하는 경우. (male과 female 중 남은 원소가 많은 배열의 원소를 건너뛴다.)

둘 중 최소값을 고르면 된다. 이러한 (i, l)조합의 계산은 반복되는 경우가 있으니 dp배열을 활용하여 기록해두고 재사용하여 연산 횟수를 줄이도록 한다.

실수

처음 통과한 코드에는 dp배열을 채우는 과정에서, 똑같은 연산을 중복해서 수행하게 하여 시간이 크게 나왔다. (건너뛰는 경우를 계산할때, 한번에 여러번 뛰는 경우도 따로 계산하였다. Top-down 방식을 사용했는데, search(i, l - 1)에 search(i, l- k)도 포함된다는 점을 놓쳤다.) 다른 사람들의 평균적인 실행시간보다 긴 내 코드의 실행시간을 보고 수정해야 겠다는 생각이 들었다.

입력

첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 줄에는 n명의 남자들의 성격이 주어진다. 그 다음 줄에는 m명의 여자들의 성격이 주어진다. 성격은 1,000,000이하의 자연수이다.

출력

첫째 줄에 성격의 차이의 합의 최솟값을 출력한다.

코드

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pull;
typedef const ll cll;
typedef queue<ll> qll;
typedef queue<pll> qpll;
typedef priority_queue<ll> pqll;
typedef priority_queue<pll> pqpll;
typedef vector<ll> vll;

cll N = 1000, M = 1000, INF = 1e9 + 1;
ll n, m, male[N] = {}, female[M] = {}, dp[N + 1][M + 1] = {{}};

ll search(ll i, ll l)
{
    if (i < 0 || l < 0)
    {
        return 0;
    }
    else if (dp[i][l] != -1)
    {
        return dp[i][l];
    }

    dp[i][l] = INF;
    dp[i][l] = min(dp[i][l], search(i - 1, l - 1) + abs(male[i] - female[l]));
    ll _i = i, _l = l, &dom = _i > _l ? _i : _l;
    if (_i != _l)
    {
        --dom;
        dp[i][l] = min(dp[i][l], search(_i, _l));
    }

    return dp[i][l];
}

int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    memset(dp, -1, sizeof(dp));
    cin >> n >> m;
    for (ll i = 0; i < n; ++i)
    {
        cin >> male[i];
    }
    for (ll i = 0; i < m; ++i)
    {
        cin >> female[i];
    }
    sort(male, male + n);
    sort(female, female + m);

    cout << search(n - 1, m - 1) << "\n";

    return 0;
}