백준 1727번 커플 만들기

문제 링크입니다: https://www.acmicpc.net/problem/1727

문제가 분류되어있는대로 정렬 + 다이나믹 프로그래밍으로 푼 문제였습니다.

알고리즘은 아래와 같습니다.

1. 남여 수치를 입력받고 오름차순 정렬을 합니다.

2. 다이나믹 프로그래밍을 진행하는데 아래와 같이 세가지 경우가 있습니다.

i) i == j인 경우 커플이 되었으므로 해당 커플의 수치 차의 절대값을 cache[i][j]에 저장해줍니다.

ii) i > j인 경우 남자가 더 많으므로 해당 커플의 수치 차의 절대값 혹은 i번째 남자를 솔로로 둡니다.

iii) i < j인 경우 여자가 더 많으므로 해당 커플의 수치 차의 절대값 혹은 j번째 여자를 솔로로 둡니다.

3. 2번을 진행한 뒤 cache[N][M]을 출력해줍니다.

#include <iostream>

#include <algorithm>

using namespace std;

 

const int MAX = 1000 + 1;

 

int N, M;

int male[MAX], female[MAX];

int cache[MAX][MAX];

 

int match(void)

{

        for (int i = 1; i <= N; i++)

                 for (int j = 1; j <= M; j++)

                 {

                         //무조건 커플

                         if (i == j)

                                 cache[i][j] = cache[i - 1][j - 1] + abs(male[i - 1] - female[j - 1]);

                         //커플 or i 번째 남자 솔로

                         else if (i > j)

                                 cache[i][j] = min(cache[i - 1][j - 1] + abs(male[i - 1] - female[j - 1]), cache[i - 1][j]);

                         //커플 or j 번째 여자 솔로

                         else if (i < j)

                                 cache[i][j] = min(cache[i - 1][j - 1] + abs(female[j - 1] - male[i - 1]), cache[i][j - 1]);

                 }

        return cache[N][M];

}

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0);

        cin >> N >> M;

 

        for (int i = 0; i < N; i++)

                 cin >> male[i];

        for (int i = 0; i < M; i++)

                 cin >> female[i];

 

        sort(male, male + N);

        sort(female, female + M);

 

        cout << match() << "\n";

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~