문제 설명
- https://www.acmicpc.net/problem/1727
- min(n,m)만큼 짝을 형성해야 합니다. 이때 min(n,m)개의 짝들의 각 값의 차이의 합이 최소가 되게 만들어야 합니다.
접근법
-
가장 먼저 남자 배열과 여자 배열을 각각 정렬한 뒤 각 배열의 최솟값끼리 짝을 만드는 방법을 생각했습니다. 하지만 이 경우 최적을 보장하지 못합니다.
[100],[1,100]의 경우 최솟값인 100과 1이 짝을 맺으면 성격 차이의 합은 99지만 100과 100이 짝을 맺으면 성격 차이의 합은 0입니다.- 그런데 재밌는건
n == m이면 최솟값끼리 짝을 만드는 방법이 곧 최적해가 됩니다.
[1,2]와[4,5]가 주어졌다면1과4, 2와5로 짝을 묶는게1과5, 2와4로 묶는 것보다 더 차이의 합이 작습니다.
이 경우앞에서 맺은 짝보다 뒤에 나보다 더 잘맞는 짝이 나오면 성립하지 않을까?라는 고민이 생깁니다.[6,7]과[1,6]이 주어졌다면 왼쪽 배열의6입장에서는 오른쪽 1과 짝이 되면 차가 5지만, 오른쪽 6과 짝이 되면 합이0으로 더 이득인거 같습니다. 하지만 이 경우 어떤 조합을 하더라도 차이의 합은 동일합니다. 즉, 오름차순으로 정렬하면 적어도 손해를 보는(반례가 발생하는)일은 없습니다. - 즉,
n == m이면서 두 배열이 정렬되어 있다면 앞에서부터 짝을 만들면 됩니다.dp[i][j]를 i번째 남자까지와 j번째 여자까지를 고려한 값이라고 정의할 때dp[i][j] = dp[i-1][j-1] + (i번째 남자와 j번째 여자의 차이)가 성립합니다.
- 그런데 재밌는건
-
이제
i > j또는j < i의 경우를 고려해야 합니다.i > j인dp[3][2]를 예로 들어보겠습니다.dp[3][2]를 채우려면 남자3명과 여자2명으로 최적해를 찾아야 합니다. 이때 경우의 수는3번이 짝을 맺었다와3번이 짝을 맺지 못했다두 가지로 나뉩니다.3번이 짝을 맺지 못했다는 곧 남자1,2번과 여자1,2번이 짝을 맺었다는 의미이며 앞에서 살펴본i == j인 경우와 동일합니다.3번이 짝을 맺었다에서 남자3번은 반드시 여자2번(가장 뒤에 값)과 짝을 맺어야 합니다. dp의 관점에서 보면 3과 2가 맺어졌으면 그 앞에 값인3-1번째 남자까지와 2-1번째 남자까지를 고현 값은 이미 구해져 있습니다.j > i인 경우는 i와j만 바꿔주면 됩니다. -
최종적으로 다음과 같은 계산이 가능합니다.
dp[i][j] = i번째 남자까지와 j번째 여자까지를 고려했을 때 최적해라고 정의했을 때
i == j면dp[i][j] = dp[i-1][j-1] + (i번째 남자와 j번째 여차의 차이)
i > j면dp[i][j] = Math.min(dp[i-1][j-1] + (i번째 남자와 j번째 여차의 차이), dp[i-1][j]
i < j면dp[i][j] = Math.min(dp[i-1][j-1] + (i번째 남자와 j번째 여차의 차이), dp[i][j-1]
정답
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
int[] manPersonality = new int[N];
int[] womanPersonality = new int[M];
st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++) {
manPersonality[i] = Integer.parseInt(st.nextToken());
}
st = new StringTokenizer(br.readLine());
for (int i = 0; i < M; i++) {
womanPersonality[i] = Integer.parseInt(st.nextToken());
}
Arrays.sort(manPersonality);
Arrays.sort(womanPersonality);
int[][] dp = new int[N+1][M+1];
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= M; j++) {
if(i == j) {
dp[i][j] = dp[i-1][j-1] + personalityDiff(manPersonality[i-1], womanPersonality[j-1]);
}else if(i > j) {
dp[i][j] = Math.min(dp[i-1][j-1] + personalityDiff(manPersonality[i-1], womanPersonality[j-1]), dp[i-1][j]);
}else if(i < j) {
dp[i][j] = Math.min(dp[i-1][j-1] + personalityDiff(manPersonality[i-1], womanPersonality[j-1]), dp[i][j-1]);
}
}
}
System.out.println(dp[N][M]);
// for (int i = 0; i < dp.length; i++) {
// System.out.println(Arrays.toString(dp[i]));
// }
}
public static int personalityDiff(int a, int b) {
return Math.abs(a-b);
}
}기타
너무 세부적으로 이건이거고 저건 저거고를 생각하지 말고
그냥 dp[i][j]는 뭐다라고 정의했을 때 해당 dp의 값으로 dp[i][j]를 만들 수 있는 방법을 찾는 방식이 더 좋을듯
냅다 dp를 정의해 버려라
