[BOJ/백준] 1727 커플 만들기

import sys
def input():
    return sys.stdin.readline().rstrip()



N,M = map(int,input().split())
MA = [0]+list(map(int,input().split()))
WA = [0]+list(map(int,input().split()))
MA.sort()
WA.sort()

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


for x in range(1,N+1):
    for y in range(1,M+1):
        if x == y:
            dp[x][y] = dp[x-1][y-1] + abs(MA[x]-WA[y])
        elif x>y:
            dp[x][y] = min(dp[x-1][y-1] + abs(MA[x]-WA[y]), dp[x-1][y])
        else:
            dp[x][y] = min(dp[x-1][y-1] + abs(MA[x]-WA[y]), dp[x][y-1])

print(dp[N][M])

이 문제는 성격의 차이의 합이 최소가 되도록 커플을 하는 것이다.

 

이 문제를 푸는 방식은 다음과 같다.

 

2차원 DP를 설정하고,  행은 남자 열은 여자를 뜻하는 것으로 하고,

 

x,y 까지 커플을 했을때, 최소 성격차를 저장했다고 하자.

 

이 문제는 사실 boj.kr/13398 하고 비슷하다고 생각한다.

 

만약 x == y가 같다면, 전부 커플이 되어야하기 때문에

dp[x][y] = dp[x-1][y-1] + abs(MA[x] - WA[y]) 가 되어야한다.

 

만약 x> y이면 우리는 남자는 커플이 될수도, 커플이 안될수 도 있다. 그러면 우리는 이중 최소값을 구해야한다.

 

이 남자가 커플이 된다하면. 위와 동일하게 dp[x-1][y-1] + abs(MA[x] -WA[y])와 동일하다.

 

이 남자가 커플로 선택되지 않으면, 이 남자의 성격은 그대로 버려지고, 이 남자가 솔로가 됬으므로, dp[x-1][y]와 동일하다.

 

이 2개의 값을 비교해서 최소값을 dp[x][y]에 넣어주면 된다.

 

x<y 일때는 여자가 더 많은 것이므로 위와 동일하게 하지만 x,y 만 바꿔주면 된다.

 

그리고 결과 적으로 dp[N][M}을 출력 해주면 된다.

 

여기서 좀 더 쉽게 풀기 위해서 남자 성격과 여자 성격의 list를 앞에 [0]을 넣어줘서 index를 편하게 해주었다.