[백준/1727] 커플 맞추기

1. 문제

1) 문제 링크

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

1727번: 커플 만들기

 

2) 설명

남자 n명, 여자 m명이 있고, 각각 점수가 매겨져 있을 때,

조건 1. 남자와 여자를 최대한 매칭시키고

조건 2. 그때 커플이 된 남녀 점수차의 합을 최소화

하는 문제다.

난이도 : Gold 3

 

2. 풀이

1) 알고리즘

    :  dp

 

2) 풀이 설명

처음에 top-down 방식으로 풀려다가 개고생했다..

뭔가 코드도 더럽고... 틀리기도 계속 틀리고...

결국 다른 사람들의 풀이를 참고했다.

 

위의 조건 1에서 남자와 여자를 최대한으로 매칭시킨다는 말은 남자 무리와 여자 무리 중 인원이 적은 쪽은 반드시 매칭시켜야 한다는 의미다.

예를 들어 남자 3명 여자 6명 있으면 커플은 최대 3쌍까지만 매칭될 수 있다. 일단 커플을 최대한 매칭시켜야 하기 때문에 무조건 세 쌍까지 매칭시켜야 한다.

 

그 이후로는 어떻게 매칭시키냐의 문제다.

일단 남자와 여자를 점수 순서대로 정렬해준다.

그 다음에는 커플들의 점수차의 합을 최소화해야하기 때문에 알맞은 점화식이 필요하다.

 

dp[x][y] 을 "남자 x명, 여자 y명이 있을 때 만들어진 커플들의 점수차 합의 최소값" 이라고 정의해보자.

말이 긴데 결국 남자 x, 여자 y명일 때 위의 조건1, 2를 만족시키는 값이라는 말이다.

 

이 dp[x][y]의 값은 3가지 경우로 나눠서 구할 수 있다.

1. x == y 인 경우

  x == y라면 남자와 여자의 수가 같다는 말이다. 그러면 조건 1에 따라(최대한 커플을 매칭시켜야하므로)

  dp[x][y] = dp[x - 1][y - 1] + abs(male[x] - female[y])

  가 된다.

2. x > y인 경우

  x > y는 남자가 여자보다 많다는 말이다. 그러므로 여자는 반드시 모두 커플이 돼야 하고 남자는 여자의 수만큼만 커플이 되면 된다.

  이때 x번째 남자는 y번째 여자와 커플이 될 수도 있고 안 될 수도 있다.(이게 x > y일 때 모든 경우의 수다)

  핵심은 x번째 남자가 y번째 여자와 커플이 안 된다고 y번 이전의 여자와 커플이 될 수는 없다는 것이다.

  왜냐하면 여자의 수가 적기 때문에 여자는 반드시 커플을 맺어야 하는데, 만약 x번째 남자가 y - 1번째 여자랑 짝을 맺으면 y번째 여자는 짝을 못 맺기 때문이다! 이는 조건 1에 맞지 않는다!

  그러므로

  dp[x][y] = min(dp[x - 1][y - 1] + abs(male[x] - female[y]) // x번 남자와 y번 여자가 커플이 되는 경우

                      , dp[x - 1][y])                                     // x번 남자와 y번 여자가 커플이 안 되는 경우

  가 된다.

3. x < y 인 경우

  이건 2번과 반대의 경우기 때문에 설명은 생략한다.

  dp[x][y] = min(dp[x - 1][y - 1] + abs(male[x] - female[y]) // x번 남자와 y번 여자가 커플이 되는 경우

                      , dp[x][y - 1])                                     // x번 남자와 y번 여자가 커플이 안 되는 경우

 

이 점화식은 남녀가 점수 순서대로 정렬되어 있다는 전제 하에 올바르게 작동한다.

만약

남자 : 10 5 1

여자 : 2  5

이런 경우에는(정렬이 안 되어있는) dp 배열이

0 0 0 

0 8 5

0 3 8

0 1 7

이런 식으로 나오게 된다. 

그럼 dp[3][2] = 7이 되니까 틀린 답이다. (제대로 된 답은 1이 나와야 한다)

이 알고리즘으로 이중 반복문을 돌고나면 결국 dp[n][m]값이 우리가 구하는 답이 된다.

3. 코드

#include <iostream>
#include <vector>
#include <math.h>
#include <algorithm>

using namespace std;

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

	int n, m;
	cin >> n >> m;
	vector<int> male(n + 1, 0);
	vector<int> female(m + 1, 0);
	vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));

	sort(male.begin(), male.end());
	sort(female.begin(), female.end());

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

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

	cout << dp[n][m] << endl;

	return 0;
}

 

 

4. 느낀점

dp에서는 탑다운 방식이 직관적이라고 생각해서 항상 탑다운으로 먼저 시도를 하는 편이다..

근데 약간 탑다운 풀이에 한계를 느낀 것 같다..

아마도 계속 잡고 있으면 탑다운으로도 맞힐 수 있을 것 같기는 한데

바텀업 풀이의 아이디어를 보면 이렇게 복잡하게 짜고 있는 탑다운 코드가 너무 야속해진다..

바텀업.. 연습하자...