https://www.acmicpc.net/problem/1727
시간 2초, 메모리 128MB

input :

• n m(1 ≤ n, m ≤ 1,000)
• 남자들의 성격
• 여자들의 성격

output :

• 성격의 차이의 합의 최솟값을 출력

조건 :

• 최대한 비슷한 성격의 사람들을 짝 지어 주기로 하였다.

• 우선 최대한 많은 커플을 만들고, 각 커플을 이루는 두 사람의 성격의 차이의 합이 최소가 되도록 하려 한다

---

이분 매칭, stable marriage 로 해결할 수 있지 않을까? 했지만. 동일한 성격의 차이를 가지는 커플에 대한 대응책이 별로 좋지 않다. 이로 인해 틀리지 않았나 생각을 한다.

다음 풀이

1. 커플의 매칭
2. 정렬?
3. 어떤 매칭

우선적으로 매칭을 해야 한다.
그 전에 입력되는 데이터의 순서에 대한 언급이 없다. 고로 정렬되어 있지 않다고 생각해야 한다.
어떤 사람이랑 매칭을 해야 할 지 모른다. 그러나 최소한 정렬이 되어 있는 상황이라면 매칭이 X자를 이루면 안 된다.

koosaga님의 답변을 보면 꼬이는 방식에 대해서 말씀하신다.

그러고 나서 냅색의 냄새가 나는 DP를 통해 해결을 하도록 가닥을 잡아야 한다.
새로운 커플을 매칭하는 것은 둘 다 새로운 인물을 추가한다는 생각으로 하기 떄문에 동일하다고 볼 수 있다.

특정인덱스 i(행), j(열)

i == j인 경우.
새로운 커플을 매칭한다. 해당하는 성격의 차이를 저장한다.

i > j인 경우.
아직까지 이미 커플이 된 놈들이 많다. i - 1 번째 행에서의 성격의 차를 가져올지.
새로운 커플을 매칭할 지 결정.

i < j인 경우.
커플이 되지 않은 사람들도 존재한다. j - 1번째 열에서의 이미 계산한 성격의 차를 가져올지.
새로운 커플을 매칭할 지 결정.

import sys

n, m = map(int, sys.stdin.readline().split())
boy = list(map(int, sys.stdin.readline().split()))
girl = list(map(int, sys.stdin.readline().split()))
ans = [[float("inf")] * (m + 1) for _ in range(n + 1)]

boy.sort()
girl.sort()

for i in range(n + 1):
    ans[i][0] = 0
for i in range(m + 1):
    ans[0][i] = 0

for x in range(1, n + 1):
    for y in range(1, m + 1):

        if x == y:
            ans[x][y] = ans[x - 1][y - 1] + abs(boy[x - 1] - girl[y - 1])
        elif x > y:
            ans[x][y] = min(ans[x - 1][y], ans[x - 1][y - 1] + abs(boy[x - 1] - girl[y - 1]))
        else:
            ans[x][y] = min(ans[x][y - 1], ans[x - 1][y - 1] + abs(boy[x - 1] - girl[y - 1]))

print(ans[n][m])