[백준/1727] 커플 만들기 (Python)

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

1727번: 커플 만들기

 

Difficulty : Gold 2

 

Status : Solved

 

Time : 00:34:18

 

---

 

문제 설명

 

 

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

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

 

 

입력 및 출력

 

입력

 

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

 

출력

 

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

 

입력 예시

 

2 1
10 20
15

 

출력 예시

 

5

 

 

---

 

풀이

 

DP 문제. 남자 i명과 여자 j명을 매칭할 때 성격차의 최솟값을 DP[i][j]라 두면...

 

• i == j : 남녀쌍이 동일하므로, 이 때의 최솟값은 (i-1, j-1 쌍을 매칭할 때의 최솟값) + (i, j번째 남녀를 매칭할 때의 최솟값)으로 정의된다. 즉 DP[i][j] = DP[i-1][j-1] + abs(man[i] + woman[j])
• i < j : 남자보다 여자가 많은 경우이므로, j번째 여자는 1. 솔로로 남거나 2. i번째 남자와 이어질 수 있다. 따라서  DP[i][j] = min(DP[i][j-1], DP[i-1][j-1] + abs(man[i] + woman[j]))
• i > j : 여자보다 남자가 많은 경우이므로, 위와 동일하다. 즉 DP[i][j] = min(DP[i-1][j], DP[i-1][j-1] + abs(man[i] + woman[j]))

 

..이런 식으로, 2차원 DP로 풀이해볼 수 있겠다. 단, 남녀 리스트는 정렬되어 있어야 한다는 점에 유의하자(그렇지 않으면 최적해가 보장되지 않기 때문이다)

 

풀이 코드

import sys
input = sys.stdin.readline
MAX = float('inf')

n, m = map(int, input().split())
man_list = list(map(int, input().split()))
woman_list = list(map(int, input().split()))
man_list.sort()
woman_list.sort()
dp = [[0]*(m+1) for _ in range(n+1)]

for i in range(1, n+1) :
  for j in range(1, m+1) :
    if i == j :
      dp[i][j] = dp[i-1][j-1] + abs(man_list[i-1] - woman_list[j-1])
    elif i < j :
      dp[i][j] = min(dp[i][j-1], dp[i-1][j-1] + abs(man_list[i-1] - woman_list[j-1]))
    else :
      dp[i][j] = min(dp[i-1][j], dp[i-1][j-1] + abs(man_list[i-1] - woman_list[j-1]))
        
print(dp[-1][-1])

풀이 완료!