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

난이도: 골드 III

문제 링크: https://www.acmicpc.net/problem/1727

1727번: 커플 만들기

 

백준 1727번 문제 커플 만들기

문제를 이해하는데 다소 어려움이 있었는데, 문제를 요약하면 다음과 같습니다.

 

• 커플의 수는 최대여야 한다. 즉 남자의 수 n, 여자의 수 m이 있을 때, 커플의 수 = min(n, m)이 된다.
• 커플을 만들었을 때, 성격의 차이를 각각 구하고, 이 값을 누적한다.
• 누적한 값이 최소가 되도록 하라.

 

다이나믹 프로그래밍 문제입니다.

입력을 두 배열 men, women에 받고, 이를 오름차순으로 정렬해야 합니다.

이후 dp 배열을 통해 계산해 나가면 답을 얻을 수 있습니다.

 

n > m일 수도 있고, n < m일 수도 있는데, 배열 men을 오가는 인덱스를 i, women을 j라고 하면,

i == j인 경우 반드시 커플이 성사됩니다.

i > j인 경우 커플이 성사될 수도 있고, 남자가 솔로로 남을 수도 있습니다.

i < j인 경우 커플이 성사될 수도 있고, 여자가 솔로로 남을 수도 있습니다.

 

커플이 성사되는 경우, dp[i][j] = dp[i-1][j-1] + abs(men[i-1] - women[j-1])이 됩니다.

솔로로 남는 경우, dp[i][j] = dp[i-1][j] (남자가 솔로로 남는 경우); dp[i][j] = dp[i][j-1] (여자가 솔로로 남는 경우)가 됩니다.

 

즉 커플이 성사되는 경우는 이전의 계산해 둔 dp배열값 + 새롭게 생성된 커플의 성격 차이값이 되는 것이며,

솔로로 남는 경우에는 이번 남자 또는 여자를 스킵하고 이전까지 누적된 성격 차이 값을 가져오는 형태입니다.

 

이후 dp[n][m]의 값을 출력하면 됩니다.

 

 

채점 결과

 

점화식에서 abs(men[i-1] + women[j-1])로 적는 어이없는 실수 때문에 두번 틀렸네요 ㅠ

DP 문제는 늘 차분하게 점화식만 잘 생각해 내면 수월하게 풀리는 것 같습니다.