1727 : 커플 만들기

풀이

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, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이

wookje.kwon's profile image

wookje.kwon

2017-12-29 17:50

Read more posts by this author