커플 만들기 C++ - 백준 1727

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

DP 문제

점화식이 LCS 문제와 유사했다.

항상 유념하는 것이지만

DP는 State를 잘 설정하는 것이 중요한 것 같다.

(사실 이 부분이 DP 문제의 전부인 것 같다.)

문제 접근

우선 커플은 $min(i,j)$ 쌍이 생길 것이다.

$DP[i][j]$ 를 남자가 $i$ 명 여자가 $j$ 명 있다고 할 때의

커플 구성 비용의 최솟값을 담고 있다 하자.

이때의 점화식의 구성을 잘 살펴보자.

만약 남자와 여자 수가 같다면 이들은 무조건 일대일로 매칭되어야 한다.

이때 남자와 여자의 성격은 정렬된 상태여야 최솟값을 얻을 수 있을 것이다.

$DP[i][j]=DP[i-1][j-1]+abs(men[i]-women[j])$ 이다.

만약 남자가 여자보다 많은 상황이라면 $i$ 번째 남자는

커플이 될 수도, 되지 않을 수도 있다.

만약 커플이 되지 않는 경우는 $i>=j$경우에서 올 것이다.

따라서 이때 점화식은 $DP[i][j]=DP[i-1][j]$이 된다.

근데 $i$ 와 $j$ 를 짝짓는 경우도 있으므로

$DP[i][j]=min(DP[i-1][j-1]+abs(men[i]-women[j])$

$,DP[i-1][j])$ 가 된다.

여자가 남자보다 많은 경우는 위 경우에서 $i<=j$ 인 경우로 고려해주면

된다.

코드는 다음과 같다.

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

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int n,m;
    cin >> n >> m;
    vector<int> a(n),b(m);
    vector<vector<int>> dp(n+1,vector<int> (m+1,0));
    for(int &t:a) cin >> t;
    for(int &t:b) cin >> t;
    sort(a.begin(),a.end());
    sort(b.begin(),b.end());
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(i==j) dp[i][j]=dp[i-1][j-1]+abs(a[i-1]-b[j-1]);
            if(i>j) dp[i][j]=min(dp[i-1][j-1]+abs(a[i-1]-b[j-1]),dp[i-1][j]);
            if(i<j) dp[i][j]=min(dp[i-1][j-1]+abs(a[i-1]-b[j-1]),dp[i][j-1]);
        }
    }
    cout << dp[n][m];
    return 0;
}