풀이
D[n][m] = 오름차순으로 남자 n명, 여자 m명을 짝짓는 최소의 값
D[n][m] = min(D[n-1][m-1] + abs(man[n] - woman[m]), D[n-1][m]) (if n > m)
D[n][m] = min(D[n-1][m-1] + abs(man[n] - woman[m]), D[n][m-1]) (if n < m)
코드
#include <stdio.h>
#include <algorithm>
using namespace std;
int abs(int a) { return a < 0 ? -a : a; }
int n, m, a[1001], b[1001], d[1001][1001];
int main() {
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; i++) scanf("%d", a + i);
for (int i = 1; i <= m; i++) scanf("%d", b + i);
sort(a + 1, a + n + 1);
sort(b + 1, b + m + 1);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
d[i][j] = d[i - 1][j - 1] + abs(a[i] - b[j]);
if (i > j) d[i][j] = min(d[i][j], d[i - 1][j]);
if (i < j) d[i][j] = min(d[i][j], d[i][j - 1]);
}
}
printf("%d", d[n][m]);
return 0;
}
아무말
백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이