BOJ 1727 커플 만들기

남자 n명과 여자 m명의 성격이 수치화 되어 정수로 주어지고, 최대한 많은 남자-여자 커플을 만들때, 성격의 차이의 합의 최소값을 구하는 문제이다.

이 문제는 정렬을 하는 것이 생각하기에도 문제 풀기에도 좋다.
성격의 차이의 합이 최소가 되도록 잘 커플을 만들어야 하는데, 성격의 차이의 합이 최소가 되려면 큰 값은 큰 값끼리, 작은 값은 작은 값끼리 매칭이 돼야하므로 남, 녀의 수치화된 성격을 각각 오름차순 정렬을 한다. 그리고 끝에서 부터, 즉 큰 값부터 매칭을 시작해보는데, 남자의 수가 더 적다고 가정하면, d[n][m]=남자 n명과 여자 m명에서 최대한 많은 커플을 만들었을 때 성격 차이의 합의 최소값 으로 두면, d[n][m]은 man[n]과 woman[m]이 커플이 된 경우 (즉,d[n-1][m-1]+abs(man[n]-woman[n]) 와 man[n]과 woman[m]이 커플이 되지 않은 경우(d[n][m-1], n이 더 작다고 가정했으므로) 이렇게 두 가지 경우로 나뉜다.

정렬 후 이런식으로 하는 것이 성립하는 이유는 나도 완벽히 깨달은 것은 아니지만 오름차순으로 정렬해놓고 보면, 예를 들면, man[n]보다 성격 수치가 작은 남자가 woman[n]같은 성격 수치가 큰 여자와 커플이 되면 man[n]이 그 여자와 커플이 될 때보다 성격 수치 차이가 커질 수 밖에 없다. 오름차순으로 정렬했기 때문에...

출처 : 백준님 강의, 백준님 강의 자료.