취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 1727번 문제인 커플 만들기이다.
문제는 아래 링크를 확인하자.

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

남자와 여자를 이어줄 때 둘의 성격의 차이를 "비용"이라 부르겠다.

먼저 남자들과 여자들의 성격수치를 각각 오름차순으로 정렬하자. 이때, $k$명의 남자와 $k$명의 여자를 고른 경우 이들을 모두 이어주면서 그 비용을 최소화하는 방법은 성격수치 순서대로 이어주는 것임을 관찰하자. (증명은 exchange argument로 할 수 있다.)

위 관찰을 이용하면, $p\ge q$이라 할 때 $p$번째 남자까지 봤을 때 $q$번째 여자까지 비용을 최소로 매칭시킬 때의 비용은 (1) $q$번째 여자를 $p$번째 남자에게 매칭시키거나, (2) 그렇지 않은 두 가지 경우가 있다는 점을 이용해 점화식을 세울 수 있게 된다. 여기서 (1)의 값을 구하고자 할 때 $q-1$번째 여자를 $p-1$이하번째 남자에게 매칭시킬 때의 최소 비용을 알아야 하는데, 이 또한 메모이제이션을 통해 반복계산을 줄여 충분히 빠르게 구할 수 있음을 관찰하자.

아래는 제출한 소스코드이다.

#include <iostream>
#include <algorithm>
using namespace std;

int N, M;
int mn[1001][1001], dp[1001][1001]; bool mvisited[1001][1001], visited[1001][1001];// [N][M]이 마지막 매칭인 최솟값
int A[1001], B[1001];

int func(int n, int m);

int mnfunc(int n, int m) {
	if (n < m) return 0x3f3f3f3f;
	if (!m) return 0;
	int &ret = mn[n][m];
	if (mvisited[n][m]) return ret;
	mvisited[n][m] = 1;
	ret = func(n, m);
	ret = min(ret, mnfunc(n - 1, m));
	return ret;
}

int func(int n, int m) {
	int &ret = dp[n][m];
	if (visited[n][m]) return dp[n][m];
	visited[n][m] = 1;
	ret = mnfunc(n - 1, m - 1) + abs(A[n] - B[m]);
	return ret;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N >> M;
	for (int i = 1; i <= N; i++) cin >> A[i];
	sort(A + 1, A + N + 1);
	for (int j = 1; j <= M; j++) cin >> B[j];
	sort(B + 1, B + M + 1);

	if (N < M) swap(N, M), swap(A, B);
	cout << mnfunc(N, M);
}

처음 이 문제를 접근할 때의 글쓴이가 했던 생각을 같이 남겨둔다.

글쓴이는 처음에 이 문제를 성격수치가 $x$인 남자와 $y$인 여자를 짝지어줄 때의 비용을 $x-y$의 절댓값으로 나타낼 때, minimum weight maximal bipartite matching의 그 가중치 총합을 구하는 문제로 보았다. 이 점에 초점을 맞춰 MCMF로 문제를 해결하려고 시도했으나, 시간초과로 해결하지 못했다. 다만, 이후에 몇몇 성질을 이용해 불필요한 간선 일부를 줄인 그래프 모델링과 MCMF로 뚫는 데에 성공하기는 했다.

헝가리안 알고리즘(Hungarian algorithm; Kuhn-Munkres Algorithm)은 구현해본 적이 없어 확인하지 않았는데 (안될 것 같지만) 이걸로도 풀릴까...?

BOJ Random Defense #10 (실패: 제한시간초과)