[백준]1727 커플만들기

1. 풀이

(1) 각 성별을 정렬한다.

남자성격과 여자성격을 정렬했을 때 총 차이의 합이 최소가 되기위해선 항상 아래의 조건이 만족한다.

(n번째남자와 매칭된 여자의 성격수치) < (n+1번째 남자와 매칭된 여자의 성격수치)

즉 아래와 같은 상황에서 선이 x자로 엇갈리는 경우는 없다.

남자성격

 1 5 7 8

ㅣㅣㅣㅣ

4 7 14 16

여자성격

 

(2) dp[i][j]=남자 i, 여자 j까지 매칭했을 때 차이의 최솟값. 구현은 다음과 같다

- 기본값

dp[i][j]=dp[i-1][j-1] + 절댓값(남자[i]-여자[i])

- i>j이면 j여자에게 잘맞는 여러명의 남자중 하나를 고른다

dp[i][j]=min(dp[i][j],d[i-1][j])

- i<j이면 i남자에게 잘 맞는 여려명의 여자중 하나를 고른다

dp[i][j]=min(dp[i][j],dp[i][j-1])

 

2. 소스코드

N,M=map(int,input().split())
man=list(map(int,input().split()))
woman=list(map(int,input().split()))

man.sort()
woman.sort()

d=[[0 for _ in range(M+1)] for _ in range(N+1)]

for i in range(1,N+1):
    for j in range(1,M+1):
        d[i][j]=d[i-1][j-1]+abs(man[i-1]-woman[j-1])
        if i>j:
            d[i][j]=min(d[i][j],d[i-1][j])
        elif i<j:
            d[i][j]=min(d[i][j],d[i][j-1])

print(d[N][M])