📚 1727 - 커플 만들기

커플 만들기

 

이해

n, m명이 있을 때 차이의 합이 최소가 되도록 하려한다.

5 4
1 2 4 4 9
3 5 6 7

: 6

4 3
1 2 4 4
3 3 3

: 3

dp와 그리디를 이용하여 풀 수 있다.

dp[i][j] = d[i-1][j-1] + 절댓값(man[i-1] + woman[j-1])

# 만약 i > j일 때는
dp[i][j] = min(dp[i][j], dp[i-1][j])

# 만약 i < j일 때는
dp[i][j] = min(dp[i][j], dp[i][j-1])

 

ex)

5 4
1 2 4 4 9
3 5 6 7

x	1	2	3	4
1	2	(4, 이전 2)	(5, 이전 2)	(6, 이전 2)
2	1	5	(이전 5, 6)	(이전 5, 7)
3	1	( 이전 5, 2)	7	(이전 7, 8)
4	1	(이전 2, 2)	(이전 7, 4)	10
5	(1, 6)	(이전 2, 5)	(4, 이전 5)	(이전 10, 6)

결국 6이라는 결과를 얻을 수 있다.

 

소스

import sys  
  
read = sys.stdin.readline  
  
n, m = map(int, read().split())  
  
man = list(map(int, read().split()))  
woman = list(map(int, read().split()))  
  
dp = [[0] * (m+1) for _ in range(n+1)]  
  
for i in range(1, n+1):  
    for j in range(1, m+1):  
        dp[i][j] = dp[i-1][j-1] + abs(man[i-1] - woman[j-1])  
        if i > j:  
            dp[i][j] = min(dp[i-1][j], dp[i][j])  
        elif i < j:  
            dp[i][j] = min(dp[i][j-1], dp[i][j])  
  
print(dp[n][m])

dp부분에서 헷갈리는 문제인 것 같다.