백준 1727 (커플 만들기) - java

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

 

문제

 

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

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

 

유형 : 정렬 + DP

 

접근 방식

• 남자와 여자 배열을 정렬한다.
• 최대한 많은 커플을 만들라는 것은 남자가 적다면 모든 남자들을, 여자가 적다면 모든 여자들을, 같다면 모든 쌍을 커플로 만들어야 한다는 것이다.
• 각 경우에 맞게 DP 배열을 2차원으로 선언하고 반복문을 통해 값을 구한다.
  • 남자가 더 작은 경우를 예로 설명하겠다. 0번째 남자는 모든 여자들과 짝을 이룰 수 있다.
  • 1번째 남자는 최소 1번째 이상의 여자하고만 짝을 이룰 수 있다. (정확히는 전에 0번째 남자가 짝을 이룬 상대보다 큰 숫자의 여성과 짝을 이뤄야 한다)
  • dp[i][j] = min( dp[i-1][0 ~ (j -1)]) + couple(i,j) 인 것이다.
  • dp[n-1][n-1] 부터 dp[n-1][m-1] 까지의 값 중 최솟값을 구하면 된다.

 

코드

import java.util.*;
import java.io.*;

public class BOJ_1727_커플_만들기 {

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

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");

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

        men = new int[n];
        women = new int[m];

        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);

        int[][] dp = new int[n][m];

        if(n <= m) {

            for(int i = 0 ; i < n ; i++) {
                for(int j = 0 ; j < m ; j++) {
                    dp[i][j] = 2_000_001;
                }
            }

            for(int i = 0 ; i < m ; i++) {
                dp[0][i] = getMinus(men[0], women[i]);
            }

            for(int i = 1 ; i < n ; i++) {
                for(int j = i ; j < m ; j++) {

                    int minNum = 2000_001;
                    for(int k = 0 ; k < j ; k++) {
                        minNum = Math.min(minNum, dp[i-1][k]);
                    }

                    dp[i][j] = Math.min(dp[i][j], getMinus(men[i],women[j]) +  minNum);
                }
            }

            int result = dp[n-1][n-1];
            for(int i = n ; i < m ; i++) {
                result = Math.min(result,dp[n-1][i]);
            }

            System.out.println(result);
        }else {

            for(int i = 0 ; i < n ; i++) {
                for(int j = 0 ; j < m ; j++) {
                    dp[i][j] = 2_000_001;
                }
            }

            for(int i = 0 ; i < m ; i++) {
                dp[i][0] = getMinus(men[i], women[0]);
            }

            for(int i = 1 ; i < m ; i++) {
                for(int j = i ; j < n ; j++) {

                    int minNum = 2000_001;
                    for(int k = 0 ; k < j ; k++) {
                        minNum = Math.min(minNum, dp[k][i-1]);
                    }
                    dp[j][i] = Math.min(dp[j][i], getMinus(men[j],women[i]) +  minNum);
                }
            }

            int result = dp[m-1][m-1];
            for(int i = m ; i < n ; i++) {
                result = Math.min(result,dp[i][m-1]);
            }

            System.out.println(result);
        }


        br.close();
    }

    static void print(int[][] dp) {
        for(int i = 0 ; i < n ; i++) {
            for(int j = 0 ; j < m ; j++) {
                System.out.print(dp[i][j]+" ");
            }
            System.out.println();
        }
        System.out.println();
    }

    static int getMinus(int curM, int curW) {
        return Math.abs(curM - curW);
    }
}