[BaekJoon] 1727 커플 만들기 (Java)

1.  문제 링크

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

2.  문제

3.  소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    static int n, m;
    static int[] manPersonality, womanPersonality;

    static void input() {
        Reader scanner = new Reader();

        n = scanner.nextInt();
        m = scanner.nextInt();
        manPersonality = new int[n + 1];
        womanPersonality = new int[m + 1];

        for(int idx = 1; idx <= n; idx++)
            manPersonality[idx] = scanner.nextInt();
        for(int idx = 1; idx <= m; idx++)
            womanPersonality[idx] = scanner.nextInt();
    }

    static void solution() {
        Arrays.sort(manPersonality);
        Arrays.sort(womanPersonality);

        int[][] dp = new int[n + 1][m + 1];
        for(int man = 1; man <= n; man++) {
            for(int woman = 1; woman <= m; woman++) {
                dp[man][woman] = dp[man - 1][woman - 1] + Math.abs(manPersonality[man] - womanPersonality[woman]);
                
                if(man > woman)
                    dp[man][woman] = Math.min(dp[man][woman], dp[man - 1][woman]);
                else if(man < woman)
                    dp[man][woman] = Math.min(dp[man][woman], dp[man][woman - 1]);
            }
        }

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

    public static void main(String[] args) {
        input();
        solution();
    }

    static class Reader {
        BufferedReader br;
        StringTokenizer st;

        public Reader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while(st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }

            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
    }
}

4.  접근

• 주어진 남자의 성격과 여자의 성격을 정렬합니다.
  • 이는 이후에 DP로 우리가 구하고자 하는 답을 구할 때, 최적 부분 구조를 만들기 위함입니다.
  • 예를 들어, 아래와 같이 성격이 존재한다고 합시다.

    남자 : 5 1 10 24
    여자 : 2 6 12 30

    • 위와 같이 성격이 존재할 때, 둘씩 매칭시킨다고 생각하면 아래와 같이 매칭이 되어야 합니다.

      남자 : 1 5 10 24
      여자 : 2 6 12 30

    • 즉, 초기에 주어진 데이터는 X자로 엇갈려 있는 부분이 존재합니다.
    • 이를 순서대로 이어주도록 하여 작은 부분 문제에서 구한 답으로 우리가 원하는 답을 구하기 위해 정렬을 해줍니다.
• dp 배열을 생성합니다.

  dp[m][w] = m번째까지의 남자와 w번째까지의 여자를 매칭을 시켰을 때 성격 차이의 합의 최소값

  • 만약 남자의 수와 여자의 수가 같다면 모든 사람이 커플로 이어져야하기 때문에 이전까지의 남자, 여자를 매칭했을 때의 성격 차이 최솟값에 현재 남자와 현재 여자를 커플로 맺어주면 됩니다.
  • 그러나, 만약 남자의 수와 여자의 수가 다르다면 많은 쪽의 몇 사람은 솔로가 되어야 합니다. 그러므로 현재 남자와 현재 여자는 서로 커플을 맺을 수도 있지만 솔로가 될 수도 있습니다.
    • 솔로가 되는 경우와 커플을 맺는 경우에서 최솟값을 선택해주며 DP 테이블을 채워나갑니다.