[1727] 커플 만들기

커플 만들기 성공

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	128 MB	1299	340	232	27.008%

문제

여자친구가 없는 남자 n명과 남자친구가 없는 여자 m명을 불러 모아서 이성 친구를 만들어 주기로 하였다. 하지만 아무렇게나 해줄 수는 없고, 최대한 비슷한 성격의 사람들을 짝 지어 주기로 하였다.

당신은 뭔가 알 수 없는 방법으로 각 사람의 성격을 수치화 하는데 성공하였다. 따라서 각 사람의 성격은 어떤 정수로 표현된다. 이와 같은 성격의 수치가 주어졌을 때, 우선 최대한 많은 커플을 만들고, 각 커플을 이루는 두 사람의 성격의 차이의 합이 최소가 되도록 하려 한다. 남자-여자 커플만 허용된다.

입력

첫째 줄에 n, m(1≤n, m≤1,000)이 주어진다. 다음 줄에는 n명의 남자들의 성격이 주어진다. 그 다음 줄에는 m명의 여자들의 성격이 주어진다. 성격은 1,000,000이하의 자연수이다.

출력

첫째 줄에 성격의 차이의 합의 최솟값을 출력한다.

예제 입력 

2 1
10 20
15

예제 출력 

5

힌트

풀다가 머리에 쥐나서.. 섬광탄 맞은 것처럼 띵~~~하게 하는 난이도네요..(라헬이..생각나고..)

처음에 dp인줄도 모르고 그리디로 풀어서 엄청 틀렸네요..

이 문제를 풀 때 꿀팁은 항상 여자 혹은 남자의 데이터 수가 많다고 생각하고 푸는 것입니다.

저는 무조건 여자가 많게 만들어서 풀었습니다.

    scanf("%d %d", &m, &g);
 
    for(int i = 0; i < m; i++) scanf("%d", data1 + i);
    for(int j = 0; j < g; j++) scanf("%d", data2 + j);
 
    if(m > g)
    {
        swap(data1, data2);
        swap(m, g);
    }
 
    sort(data1, data1 + m);
    sort(data2, data2 + g);

인풋과 정렬까지 하는 부분입니다.

만약 m(남자)가 크면 g(여자)와 swap을 해서 데이터를 바꿔줍니다.

남자의 데이터(1, 2, 3, 4), 여자의 데이터(a,b,c,d,e,f,g)라고 가정하겠습니다.

1

2

3

4

1가 선택할 수 있는 여자는 a,b,c,d입니다.

a

b

c

d

e

f

g

2가 선택할 수 있는 여자는 b,c,d,e입니다.

a

b

c

d

e

f

g

3이 선택할 수 있는 여자는 c,d,e,f입니다.

a

b

c

d

e

f

g

4가 선택할 수 있는 여자는 d,e,f,g입니다.

a

b

c

d

e

f

g

dp는 2차원으로 정의합니다.

dp[남자][여자] = 남자가 여자를 선택했을 때 까지 궁합의 합의 최솟값입니다.

예를 들어 1번 남자가 b번 여자를 선택한다면 2번 남자는 c,d,e만 선택할 수 있습니다.

dp[1][a]는 (1번 남자 성격) - (a번 여자 성격)의 절대값입니다.

그리고 dp[1][b]는 (1번 남자 성격) - (b번 여자 성격)의 절대값과 dp[1][a] 둘 중에 작은 값을 선택해서 저장합니다.

이 작업을 dp[1][d]까지 반복합니다.

점화식으로 표현하면 이 부분은 i == 0일 때 입니다.

    for(int i = 0; i < m; i++)
    {
        if(i == 0)
        {
            dp[0][0] = abs(data1[0] - data2[0]);
 
            for(int j = 1; j < g - (m - i - 1); j++) dp[i][j] = min(dp[i][j - 1], abs(data1[0] - data2[j]));
        }

이후에 2-b를 연결한다고 생각하면 2-b의 절대값에 1-a를 더합니다. 그리고 dp[2][b]에 그 값을 저장합니다.

2-c를 연결한다고 생각하면 2-c의 절대값을 구하여서 dp[1][b]까지의 최솟값에 더하고 dp[2][b]값과 비교하여 작은 값을 저장합니다.

이 부분이 핵심이며.. 이 작업을 반복하면 정답을 구할 수 있습니다.

        else
        {
            for(int j = i; j < g - (m - i - 1); j++)
            {
                if(j == i) dp[i][j] = dp[i - 1][j - 1] + abs(data1[i] - data2[j]);
                else dp[i][j] = min(dp[i - 1][j - 1] + abs(data1[i] - data2[j]), dp[i][j - 1]);
            }
        }

아래는 풀 코드입니다.

#include <iostream>
#include <algorithm>
#include <vector>
#include <string.h>
#include <cstdio>
#include <stack>
 
#define ull unsigned long long
#define ll long long
#define mp make_pair
#define MAX_SIZE 1010
#define MAX_MOVE 31
 
using namespace std;
 
typedef pair<int, int> p;
 
int data1[MAX_SIZE];
int data2[MAX_SIZE];
int dp[MAX_SIZE][MAX_SIZE];
int m, g;
 
int abs(int a)
{
    if(a>=0) return a;
    else return -a;
}
 
int main()
{
    scanf("%d %d", &m, &g);
 
    for(int i = 0; i < m; i++) scanf("%d", data1 + i);
    for(int j = 0; j < g; j++) scanf("%d", data2 + j);
 
    if(m > g)
    {
        swap(data1, data2);
        swap(m, g);
    }
 
    sort(data1, data1 + m);
    sort(data2, data2 + g);
 
    for(int i = 0; i < m; i++)
    {
        if(i == 0)
        {
            dp[0][0] = abs(data1[0] - data2[0]);
 
            for(int j = 1; j < g - (m - i - 1); j++) dp[i][j] = min(dp[i][j - 1], abs(data1[0] - data2[j]));
        }
        else
        {
            for(int j = i; j < g - (m - i - 1); j++)
            {
                if(j == i) dp[i][j] = dp[i - 1][j - 1] + abs(data1[i] - data2[j]);
                else dp[i][j] = min(dp[i - 1][j - 1] + abs(data1[i] - data2[j]), dp[i][j - 1]);
            }
        }
    }
 
    printf("%d\n", dp[m - 1][g - 1]);
 
    return 0;
}