[BAE/<JOON> 문제풀이] 1727. 커플 만들기

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

1727번: 커플 만들기

서론

코너 케이스 만들기 그나마 편한 문제였다. 작은 입력으로 코너 케이스가 구현된다는 것 자체가 감사하다.

풀이

커플부터 최대한 많이 만들어야 하므로 커플 쌍은 반드시 min(남자 수, 여자 수) 가 된다.

또한 각 성별 성격수치를 오름차순 정렬하면 남녀를 대응시킬 때 순차적으로 대응시켜도 반례가 발생하지 않는다.

왜냐하면 차이의 합이라는건 남자 군집 a의 합과 여자 군집 b의 합의 차이와 똑같기 때문이다. 연산 순서만 달라졌을 뿐이다.

이 말인즉슨, i 번 남자와 j번 여자를 짝지었을 때 i + 1 번째 남자는 j + 1 번보다 인덱스가 작은 여자와는 대응시키지 않아도 된다는 뜻이다. 어차피 계산값은 똑같을 것이기 때문이다.

 

남자 여자 수가 같은 경우는 1가지 경우 수 밖에 없으므로 수가 차이나는 경우를 생각해보자.

사람 수가 적은 성별은 반드시 모든 사람이 커플이 되어야한다.

사람 수가 많은 성별은 사람이 남으므로 적절한 짝을 골라줘야한다.

첫 문단의 규칙을 적용하면 각 사람마다 짝이 될 수 있는 이성의 범위를 정할 수 있다.

사람이 적은 성별의 i번째 사람이 짝될 수 있는 범위는 i ~ i + 두 성별간 사람 차이수 까지다.

왜냐하면 반드시 모든 사람이 맺어져야하므로 앞사람과 뒷사람을 위한 선택지를 남겨놔야하기 때문이다.

그림으로 나타내면 아래와 같다.

만약 이 범위를 벗어나면 비둘기집 원리로 인해 앞사람과 뒷사람 중 맺어지지 못하는 사람이 반드시 생긴다.

따라서 이렇게 점화식을 구상할  수 있다.

DP[i][j] = i번째 사람과 j번째 사람을 맺었을 때 성격차이 합의 최솟값

DP[i][j] = min(DP[i - 1][(i ~ j) - 1] + arr[i][i~j])

내가(i번째 사람이) j 번째 상대방을 골랐을 때 이전까지의 최적값은 DP[i - 1][j - 1]에 들어있으니 그 값과 비교 계산하는 식이다.

뭔가 그리디가 섞여서 설명이 너무 어려워지는 것 같다.

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdlib>
using namespace std;
using ll = long long;
const ll mod = 10007;
struct p {
    int j, c;
};
// 두 배열을 정렬했으므로 최적일 때 인덱스는 절대 꼬이지 않음.
int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n, m; cin >> n >> m;    
    vector<int> mp(n + 1), fp(m + 1); // dp[i][j] = minimum sum of diff when ith male - jth female is matched
    for (int i = 1; i <= n; i++) {
        cin >> mp[i];
    }    
    for (int i = 1; i <= m; i++) {
        cin >> fp[i];
    }    
    if (n > m) {
        int tmp = n; n = m; m = tmp;
        auto t = mp; mp = fp; fp = t;
    }
    vector<vector<int>> dp(n + 1, vector<int>(m + 1, 2100000000)), arr(n + 1, vector<int>(m + 1));
    for (int i = 1; i <= n; i++) {        
        for (int j = 1; j <= m; j++) {
            arr[i][j] = abs(mp[i] - fp[j]);
        }
    }    
    for (int i = 0; i <= n; i++) {
        dp[i][0] = 0;
    }
    for (int i = 0; i <= m; i++) {
        dp[0][i] = 0;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = i; j <= m - (n - i); j++) {            
            for (int k = j; k >= j - (m - n); k--) {
                if (k < i) break;
                int s1 = dp[i - 1][k - 1] + arr[i][k];
                dp[i][j] = dp[i][j] < s1 ? dp[i][j] : s1; 
            }
        }
    }    
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            //cout << dp[i][j] << " ";
        }
        //cout << "\n";
    }
    //cout << *min_element(dp[n].end() - (m - n) - 1, dp[n].end());
    cout << dp[n][m];
    return 0;
}