C++[백준]1727번 커플 만들기

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

1727번: 커플 만들기

 

솔루션

---

해당 문제를 접하기 전에 먼저 풀었던 문제가 있는데, (https://www.acmicpc.net/problem/8902) 

그 문제와 유사해서 접근은 금방 할 수 있었다.

 

먼저 남/여 중 더 적은 것은 v0배열에 담고, 다른 것은 v1 배열에 담는다

그리고 각각 정렬을 해 준다.

이를 통해 i <-> j +1 과 i+1 <-> j일 경우는 없어지며, (꼬인 형태로 매칭되지 않으며) 남은 부분의 해가 최적해가 될 수 있도록 할 수 있다. 즉 dp이다.

 

 

남/여 쌍을 무조건 최대로 맞춰야하기 때문에,

v0의 원소는 무조건 다 매칭 되어야 한다.

 

그리고 v0의 i명과, v1의 j명이 매칭이 됐을 때, 남은 N- i명, M-j 명이 매칭이 되었을 때의 최소값을 저장을 한다.

 

나는 재귀식으로 dp를 짰는데

1. i에서 j의 원소와 매칭을 하는 경우 -> 성격 차이를 계산 + 재귀 i+1, j+1을 호출

2. i에서 j의 원소와 매칭하지 않는 경우 -> 0 + 재귀 i, j+1을 호출

 

따라서 점화식은  dp[i][j] = min ( func(i+1,j+1) + 성격차이, func(i, j+1) ) 로 세울 수 있다.

그리고 기저상황은

1. i의 원소가 무조건 매칭되어야 하므로 v0에 남은 사람이 더 많은 경우 -> 무한대 리턴

2. i가 다 매칭 된 경우 -> 0 리턴

3. 이미 방문한 dp 배열이라면 -> dp배열 리턴

 

 

 

코드

---

#define INF 210000000000;
#define ll long long int
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

int N, M;
ll dp[1002][1002];
vector<int> v0;
vector<int> v1;

ll solve(int i, int j) {
	//남은 i의 수가 더 많으면 안됨.
	if (v0.size() - i > v1.size() - j) return dp[i][j] = INF;
	
	//짝을 다 맞췄으면 리턴.
	if (i == v0.size()) return 0;
	
	//이미 방문했더라면, 리턴
	if (dp[i][j] != 0) return dp[i][j];

	ll& ref = dp[i][j] = INF;
	//짝을 맞춰주는 경우
	ref = min(solve(i + 1, j + 1) + abs(v0[i] - v1[j]), ref);
	
	//다음 짝을 맞추는 경우
	ref = min(solve(i, j + 1), ref);
	return ref;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	cin >> N >> M;

	int value;
	if (N > M) {
		for (int i = 0; i < N; i++) {
			cin >> value;
			v1.push_back(value);
		}
		for (int j = 0; j < M; j++) {
			cin >> value;
			v0.push_back(value);
		}
	}
	else {
		for (int i = 0; i < N; i++) {
			cin >> value;
			v0.push_back(value);
		}
		for (int j = 0; j < M; j++) {
			cin >> value;
			v1.push_back(value);
		}
	}
	sort(v0.begin(), v0.end());
	sort(v1.begin(), v1.end());

	cout << solve(0, 0) << '\n';
}