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

문제

여자친구가 없는 남자 n명과 남자친구가 없는 여자 m명을 불러 모아서 이성 친구를 만들어 주기로 하였다. 하지만 아무렇게나 해줄 수는 없고, 최대한 비슷한 성격의 사람들을 짝 지어 주기로 하였다.

당신은 뭔가 알 수 없는 방법으로 각 사람의 성격을 수치화 하는데 성공하였다. 따라서 각 사람의 성격은 어떤 정수로 표현된다. 이와 같은 성격의 수치가 주어졌을 때, 우선 최대한 많은 커플을 만들고, 각 커플을 이루는 두 사람의 성격의 차이의 합이 최소가 되도록 하려 한다. 남자-여자 커플만 허용된다.

 

 

 

 

내 생각

문제 요약

1. 남자 n명, 여자 m명을 짝지어주는데 비슷한 성격의 사람들로 짝 지어주려고 한다.

2. 성격의 수치로 계산하여 남-여 짝지어준다.

3. 최대한 많은 커플, 그리고 각 커플을 이루는 두 사람의 성격의 차이의 합은 최소

 

 

핵심은 정렬! 정렬을 해야한다 ! 정렬을 해서 성격 차이 계산을 더 쉽게 해야 한다! 

남자 i명, 여자 j명까지 매칭을 하고 성격의 차이의 최솟값을 dp에 담는다.

 

 

입력

첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 줄에는 n명의 남자들의 성격이 주어진다. 그 다음 줄에는 m명의 여자들의 성격이 주어진다. 성격은 1,000,000이하의 자연수이다.

출력

첫째 줄에 성격의 차이의 합의 최솟값을 출력한다.

 

Input)

2 1

10 20

15

Output)

5

 

 

 

* 참고

abs()

 : 절대값을 반환

 

 

 

내 코드

n, m = map(int, input().split())
male = list(map(int, input().split()))
female = list(map(int, input().split()))

male.sort()
female.sort()

dp = [[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]: 첫 번째 남자 i명과 첫 번째 여자 j명을 매칭했을 때의 최소 성격 차이의 합
        # 현재 남자와 여자의 성격 차이를 더해줌
        dp[i][j] = dp[i-1][j-1] + abs(male[i-1] - female[j-1])
        # 여자가 더 적은 상황
        if i > j:
            dp[i][j] = min(dp[i][j], dp[i-1][j])
        # 남자가 더 적은 상황
        elif i < j:
            dp[i][j] = min(dp[i][j], dp[i][j-1])

print(dp[n][m])