[백준/BOJ] 1727. 커플 만들기 [Gold 3]

1727. 커플 만들기

문제출처 : https://www.acmicpc.net/problem/1727

code

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

int main()
{
	int n, m;
	cin >> n >> m;
	int man[1001];
	int woman[1001];
	int arr[1001][1001];

	for (int i = 1; i <= n; i++)
		cin >> man[i];
	for (int i = 1; i <= m; i++)
		cin >> woman[i];

	sort(man+1, man+1+n);
	sort(woman+1, woman+1+m);

	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			arr[i][j] = arr[i - 1][j - 1] + abs(man[i] - woman[j]);
			if (i < j)
				arr[i][j] = min(arr[i][j], arr[i][j - 1]);
			else if (i > j)
				arr[i][j] = min(arr[i][j], arr[i - 1][j]);
		}
	}

	cout << arr[n][m];

	return 0;
}

처음엔 진짜 단순하게 배열을 반복문으로 돌면서 휩쓸면서 지나가면 최적의 값이 나오겠거니 생각했는데, 예외 상황도 있어서 난항을 겪었다.

예전에도 가끔씩 나온문제지만, dp(dynamic programming)를 이용해서 푸는 문제였다.

다이나믹 프로그래밍의 개념은 정확하게는 몇개가 있지만,
내가 이해한 다이나믹 프로그래밍은
1. 비슷한 절차를 반복하는경우
2. 실시간으로 값을 초기화 해가는경우
에 dp를 적용시킬 수 있는것 같다.(ㅈㄴ야매라서 틀릴수도있다.)

얼핏보면 재귀함수랑 똑같은것 같지만, 실시간으로 값을 바꿔가는것에서 차이가 있다.(그래서 동적프로그래밍이다.)

dp로 예를드는것중 피보나치수열을 가장 많이드는것 같다.

1 1 3 5 8.....

앞 두숫자를 더해서 수열에 추가하고, 그 숫자와 그 전숫자를 또 더해서 수열에 추가하고... 를 반복해서 만드는 수열이다.

비슷한 절차를 반복하고, 실시간으로 값이 바뀌기 때문에 dp에 알맞은 예인것 같다.

dp까지는 그렇다치고... 말대로 구현하기가 참 어려웠던것같다. ㅠㅠ
dp문제 더많이 풀어봐야지...