[python] 백준 1727 커플 만들기

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

1727번: 커플 만들기

 

문제 해결

• 커플 만드는 문제
• 최근 코딩테스트에서 나오는 문제 유형이다.(사실 이것보다 더 어렵다.ㅠㅠ)
• 시간복잡도 신경쓰면서 커플을 연결하는 것이 쉽지 않다.
• 구하고자 하는 것은 성격의 차이의 합이 최소가 되는 것이다. 따라서 누적합을 통해 답을 도출하도록 한다.
• sort를 통해 성격을 수치화한 것을 오름차순으로 만든 다음 남자 0번과 가장 맞는 여자 j(0<=j<=m-n)번을 찾은 다음 1번은 여자 j+1번부터 찾고 하면서 최적의 해를 찾으면 된다.

 

CODE

import sys
input = sys.stdin.readline
n, m = map(int,input().split()) # 솔로남자, 솔로여자
M = list(map(int, input().split()))
W = list(map(int, input().split()))
if n >m:
    M, W = W, M
    n, m = m, n
dp = [[0]*m for _ in range(n)]
M.sort(); W.sort()

dp[0][0] = abs(M[0]-W[0])
for j in range(1,m-(n-1)):
    dp[0][j] = min(abs(M[0]-W[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(M[i]-W[j])
        else:
            dp[i][j] = min(dp[i-1][j-1]+abs(M[i]-W[j]),dp[i][j-1])
print(dp[n-1][m-1])