BOJ_1727_커플 만들기 (Java)

[Gold II] 커플 만들기 - 1727

문제 링크

성능 요약

메모리: 20392 KB, 시간: 140 ms

분류

다이나믹 프로그래밍, 그리디 알고리즘, 정렬

제출 일자

2025년 2월 23일 23:34:57

문제 설명

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

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

입력

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

출력

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

문제 풀이

풀이가 꽤 난해했다. 인원 짝이 맞으면 정렬해서 다 연결하면 되겠지만 그게 안된다. N과 M이 달라 그때그때 최적의 선택을 해줘야하면서 모든 경우의 수를 고려해야한다. 일단 같은 개수일 땐 이전 1명씩 덜 골랐을때 최적값에서 이번 차이를 더한다. 그러나 인원수 차이날땐 예를들어 i > j일때 이번에 i를 안 고른 최적값인 dp[i-1][j]값이 최적일수도 있고, 혹은 둘 다 안고른 상태에서 이번의 차이를 더해주는 dp[i-1][j-1] + 차이값이 최적일수도 있다. 이를 모두 고려해야한다.

코드

/**
 * Author: nowalex322, Kim HyeonJae
 */

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

public class Main {
    static BufferedReader br;
    static BufferedWriter bw;
    static StringTokenizer st;
    static int N, M, A[], B[], dp[][];
    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    public void solution() throws Exception {
        br = new BufferedReader(new InputStreamReader(System.in));
//        br = new BufferedReader(new InputStreamReader(new FileInputStream("src/main/java/BOJ_1727_커플만들기/input.txt")));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));

        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        A = new int[N+1];
        B = new int[M+1];
        dp = new int[N+1][M+1];
        for(int i=1; i<=N; i++) {
            for(int j=1; j<=M; j++) {
                dp[i][j] = Integer.MAX_VALUE;
            }
        }
        for(int i = 0; i <= N; i++) {
            dp[i][0] = 0;
        }
        for(int j=0; j <= M; j++) {
            dp[0][j] = 0;
        }

        st = new StringTokenizer(br.readLine());
        for(int i=1; i<=N; i++) {
            A[i] = Integer.parseInt(st.nextToken());
        }
        st = new StringTokenizer(br.readLine());
        for(int i=1; i<=M; i++) {
            B[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(A, 1, N+1);
        Arrays.sort(B, 1, M+1);

        dp[0][0] = 0;
        for(int i=1; i<=N; i++) {
            for(int j=1; j<=M; j++) {
                // 이번에 양쪽 수 맞을때 최대한 많이 매칭 (정렬해서 최적 가정)
                if(i == j) dp[i][j] = Math.min(dp[i][j], dp[i-1][j-1] + Math.abs(A[i] - B[j]));

                // 남자 > 여자
                else if(i > j) dp[i][j] = Math.min(dp[i][j],
                        Math.min(dp[i-1][j], // 이번에 선택안함
                                dp[i-1][j-1] + Math.abs(A[i] - B[j]))); // 이번커플매칭
                // 여자 > 남자
                else dp[i][j] = Math.min(dp[i][j],
                            Math.min(dp[i][j-1], // 이번에 선택안함
                                    dp[i-1][j-1] + Math.abs(A[i] - B[j]))); // 이번커플매칭
            }
        }

        System.out.println(dp[N][M]);
        bw.flush();
        bw.close();
        br.close();
    }
}