[PS] 백준 1727번 커플만들기

고범수·2023년 3월 21일
0

Problem Solving

목록 보기
29/31

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

문제 설명

남자 n명, 여자 m명이 있을 때, 최대한 많이 짝지어 준 후에 짝끼리의 성격 차의 합이 최소가 되게 하려 한다. 이 때 최소를 구하는 문제이다.

문제 풀이

도저히 풀 수 없어 풀이를 보고 말았다. 다이나믹 프로그래밍으로 풀 수 있다. 우선 제일 중요한 dp 테이블에 무엇을 담을 것인가는 아래와 같다. 그리고 이 구조를 가지고 푸는 dp 문제가 굉장히 많기 때문에 피할 수 없다.

dp[i][j] := 남자(1~i번)과 여자(1~j번)만 있는 경우의 성격 차의 최소 값

그렇다면 점화식은 어떻게 될까?
아래의 예시를 살펴보자

번호 1 2 3 4 5
남자 1 3 5 7
여자 2 5 6 8 10

인 경우에 dp[4][4]까지 구해져 있다고 가정하자. 이 상황에서 5번 여자를 포함해서 최소를 구하려 한다. 그렇다면 당연하게 5번 여자를 짝 지어주는 경우와 짝 지어주지 않는 경우로 나뉘고, 짝 지어주는 경우, 기존의 여자중 누군가는 솔로가 되게 된다. 다만 솔로가 되는 부분은 간단하게 구할 수 있다.
1. 추가된 5번 여자를 짝 지어주지 않는 경우는 이미 구해져 있는 dp[4][4]와 같다. 현재 dp[i][j]였다면, 아래와 같다.

dp[i][j] = dp[i][j-1];

남자가 더 많다면 다음과 같다.

dp[i][j] = dp[i-1][j];


2. 추가된 5번 여자를 짝 지어주는 경우. 이 경우는 생각이 조금 필요하다. 몇번 남자와 짝 지어줄 것인가? 이 부분에서 최적부분구조 문제가 발생한다. 이전에 구해놓은 dp[4][4], dp[4][3] ... dp[1][1] 의 해를 수정하지 않으면서 답을 구해야 한다.
만약 성격수치로 오름차순 정렬을 했다면 가장 마지막 남자와 짝을 지어주면 된다. 오름차순 정렬을 하였다면 차이를 최소화 시키기 위해서는 성격수치가 큰 사람끼리 짝이 되어야 하기 때문이다. 따라서 이 경우, 마지막 남자와 짝 지어주고 성격차를 구한다. 그리고 나머지 인원에 대해서 성격차의 최소를 구한다(점화식에 의해 이미 구해져있다.)

dp[i][j] = dp[i-1][j-1] + Math.abs(men[i] - women[j])

만약 정렬을 하지 않았다면 현재 고려중인 i명의 남자와 j명의 여자중에서 누구와 짝을 지어야 최소가 되는지 알 수 없을 뿐더러 반복문을 돌려 알아냈다 하더라도 dp[i-1][j-1]의 값을 다시 계산해야 하므로 정렬을 하여 최적부분구조를 만들어야한다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;

    static int n, m;
    static int[] men, women;
    static int[][] dp;

    public static void main(String[] args) throws Exception {
        st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        men = new int[n];
        women = new int[m];
        dp = new int[n + 1][m + 1];

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            men[i] = Integer.parseInt(st.nextToken());
        }

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < m; i++) {
            women[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(men);
        Arrays.sort(women);

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                dp[i][j] = dp[i - 1][j - 1] + Math.abs(men[i - 1] - women[j - 1]);


                if (i > j) {
                    dp[i][j] = Math.min(dp[i][j], dp[i - 1][j]);
                } else if (i < j) {
                    dp[i][j] = Math.min(dp[i][j], dp[i][j - 1]);
                }
            }
        }

        System.out.println(dp[n][m]);
    }

}

0개의 댓글