백준 1727 : 커플 만들기

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

1727번: 커플 만들기

[ 문제풀이 ]

최적화 문제는 그리디, DP, 파라메트릭 서치 중 하나라고 생각하기 때문에 처음에는 그리디로 접근하였는데 틀렸습니다가 나와서 DP로 해결하였다.

먼저 dp 테이블을 다음과 같이 정의하자.

dp[i][j] : (1~i)까지의 남자와 (1~j)까지의 여자를 커플 매칭했을때 성격 차이 최소값

 

그렇다면 점화식은 어떻게 될까?

남자(i), 여자(j)의 수가 같다면 모두 커플이 이루어져야 하기 때문에 이전 남자(i-1), 여자(j-1)를 커플 매칭한 성격 차이 최솟값에 i번째 남자와 j번째 여자를 커플 맺어주면 된다.

그렇다면 남자(i), 여자(j)의 수가 다르다면 어떻게 해야할까?

남자(i)가 여자(j)보다 많다면 추가된 i번째 남자는 커플을 맺거나 솔로가 되어야 한다. 반대로 남자(i)가 여자(j)보다 적다면 추가된 j번째 여자는 커플을 맺거나 솔로가 되어야 한다.

따라서 둘 중 최솟값을 선택해주면 된다.

 

다만, dp 테이블을 채우기 전에 남자와 여자를 정렬해줘야 한다. 정렬해주지 않으면 다음과 같은 반례가 발생하게 된다.

3 3
3 5 5
4 4 2

 

나는 반례를 통해서 정렬을 해줘야겠다고 생각했지만 실제 정렬을 하는 이유는 DP를 사용하기 위한 조건 중 하나인 최적 부분 구조가 성립해야 하기 때문이다.

https://www.acmicpc.net/board/view/9030

정확한 이유는 위 글을 참고하면 된다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
	
	public static void main(String[] args) {
		try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
			BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out))) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int n = Integer.parseInt(st.nextToken());
			int m = Integer.parseInt(st.nextToken());
			int[] man = new int[n + 1];
			int[] woman = new int[m + 1];
			st = new StringTokenizer(br.readLine());
			for (int i = 1; i <= n; ++i) {
				man[i] = Integer.parseInt(st.nextToken());
			}
			st = new StringTokenizer(br.readLine());
			for (int i = 1; i <= m; ++i) {
				woman[i] = Integer.parseInt(st.nextToken());
			}
			
			Arrays.sort(man);
			Arrays.sort(woman);
			
			//dp[i][j] : (1~i)까지의 남자와 (1~j)까지의 여자를 커플 매칭했을때 성격 차이 최소값
			int[][] dp = new int[n + 1][m + 1];
			for (int i = 1; i <= n; ++i) {
				for (int j = 1; j <= m; ++j) {
					//i번 남자와 j번 여자 커플 매칭
					dp[i][j] = dp[i - 1][j - 1] + Math.abs(man[i] - woman[j]);
					//남자가 더 많으면 추가된 i번 남자 솔로
					if (i > j) dp[i][j] = Math.min(dp[i][j], dp[i - 1][j]);
					//여자가 더 많으면 추가된 j번 여자 솔로
					else if (i < j) dp[i][j] = Math.min(dp[i][j], dp[i][j - 1]);
				}
			}
			bw.write(dp[n][m] + "\n");
		} catch (Exception e) {
			e.printStackTrace();
		}
	}
}