BOJ 1727 커플만들기(C++)

커플 만들기 성공

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	128 MB	817	216	145	27.938%

문제

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

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

입력

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

출력

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

예제 입력 

2 1
10 20
15

예제 출력 

5

힌트

출처

• 문제를 번역한 사람: author10

알고리즘 분류

• 다이나믹 프로그래밍
• 정렬

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38

#include    <cstdio> #include    <algorithm> #pragma warning (disable : 4996)   int men[1111]; int women[1111]; int D[1111][1111]; int main() {     int n, m;     scanf("%d %d", &n, &m);       for (int i = 1; i <= n; ++i)         scanf("%d", &men[i]);     for (int i = 1; i <= m; ++i)         scanf("%d", &women[i]);     std::sort(men + 1, men + 1 + n);     std::sort(women + 1, women + 1 + m);       for (int i = 1; i <= n; ++i)     {         for (int j = 1; j <= m; ++j)         {             if(i==j) //무조건 1:1 매칭인 경우                 D[i][j] = D[i - 1][j - 1] + std::abs(men[i] - women[j]);             else if (i > j) // 남자가 많은 경우에 이럴 수 있음.             {                 D[i][j] = std::min(D[i - 1][j - 1] + std::abs(men[i] - women[j]), D[i - 1][j]);             }             else //여자가 많을 경우에 가능             {                 D[i][j] = std::min(D[i - 1][j - 1] + std::abs(men[i] - women[j]), D[i][j - 1]);             }           }     }     printf("%d", D[n][m]);     return 0; }

다이나믹 프로그래밍 문제. 

풀긴 풀었는데 아직도 조금 헷갈린다. 

D[i][j]는 i명의 남자와 j명의 여자가 커플이 되었을 때의 성격차이의 합의 최소값이라고 한다면 

더 적은쪽은 무조건 매칭이 다 되야 한다. 

i와 j가 같은 경우 사실 선택권이 없다. 

둘다 정렬했을 경우 

남 5 10 15 20 

여 7 18 22 35 

같은 경우 

5와 18 / 10과 7 이런식으로 교차로 매칭이 된다면 순차적으로 매칭되는 5-7 / 10-18보다 분명 성격차가 커질 것이기 때문이다.

때문에 신경쓸 것은 i < j 일 경우 혹은 j > i일 경우 더 많은 쪽에서 한사람을 포기해야 하는데 누구를 포기하는게 가장 적은 성격차이가 되는지 보면 된다.

남 5 10 15 20

여 7 18 22 

일 경우 

22와 15, 22와 20를 체크해보면 된다. 

이때 7-5는 매칭, 18-10은 매칭이므로 15-22의 성격차와 20-22의 성격차 비교하였다.