[백준][Python] 1727 커플 만들기

일단 n을 무조건 수가 적은쪽으로 통일 시킨 후

dp로 각각 짝을 지어줬을 시 차이가 min인 값을 누적시킵니다.

앞인자는 수가 적은쪽의 인자고 뒤 인자는 수가 많은쪽의 인자입니다.

m - (n - 1)은 수가 큰거에서 작은 것을 빼고 1을 더해준 값으로

선택할 수 있는 m쪽 인자의 index 범위를 뜻합니다.

 

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
boys = list(map(int, input().split()))
girls = list(map(int, input().split()))
if n > m: 
    boys, girls = girls, boys
    n, m = m, n
dp = [[0] * m for __ in range(n)]
boys.sort(); girls.sort()

dp[0][0] = abs(boys[0] - girls[0])
for j in range(1, m - (n - 1)):
    dp[0][j] = min(abs(boys[0] - girls[j]), dp[0][j - 1])
    
for i in range(1, n):
    for j in range(i, m - (n - i - 1)):
        if i == j:
            dp[i][j] = dp[i - 1][j - 1] + abs(boys[i] - girls[j])
        else:
            dp[i][j] = min(dp[i - 1][j - 1] + abs(boys[i] - girls[j]), dp[i][j - 1])
print(dp[n - 1][m - 1])