백준 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. 소스코드