백준(BOJ) 1727 커플 만들기 **

어렵지 않은 DP 문제

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <math.h>
#include <queue>
#include <set>
#include <list>
#include <utility>
#include <functional>
#define MAX 1005
#define INF 987654321
#define MOD 1000000
#pragma warning(disable:4996)
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;

int a, b;
int m[MAX], w[MAX], dp[MAX][MAX];

int main()
{
	scanf("%d %d", &a, &b);
	for (int i = 1; i <= a; i++)
		scanf("%d", &m[i]);
	for (int i = 1; i <= b; i++)
		scanf("%d", &w[i]);
	sort(m + 1, m + 1 + a), sort(w + 1, w + 1 + b);
	if (a > b)
		swap(a, b), swap(m, w);
	for (int i = 1; i <= a; i++)
		for (int k = i; k <= b; k++)
		{
			int tmp = abs(m[i] - w[k]);
			//printf("<%d>", tmp);
			if (k == i)
				dp[i][k] = tmp + dp[i - 1][k - 1];
			else
				dp[i][k] = min(dp[i][k - 1], (dp[i - 1][k - 1] + tmp));
		}
	printf("%d", dp[a][b]);
	return 0;
}