petermoon12   9달 전

DP로 어떻게 접근해야하는지 생각이 나지 않아서, 정렬 후에 다음항과 비교하여 차이가 작은 값을 더해나갔는데..

어떤 예외가 존재하는지 모르겠습니다.


DP로는 어떻게 풀 수 있을까요...ㅜ

chatterboy   9달 전

항상 n >= m이라고 한다면, m명의 커플을 무조건 만들어야 합니다.

따라서, 점화식을 세워본다면

T[i][j] = a[1...i]와 b[1...j]를 고려했을 때, 최적값이라고 한다면 ( 1<=i<=n, 1<=j<=m )

T[i][j] = min(T[i-1][j], T[i-1][j-1] + |a[i]-b[j]|)

로 나타낼 수 있습니다.

여기서 항상 m명을 뽑았는지에 대한 처리만 해주시면 가능합니다.


petermoon12   9달 전

음.. 우선 답변 감사드립니다ㅠ

그런데 점화식을 봐도 잘 이해가 되지 않습니다.

T배열에 저장하는 것이랑 제가 했던 바와 같이 sum변수에 저장해나가는 것 하고 무슨 차이가 있을까요..ㅜ?

어차피 정렬된 상태인데요...

댓글을 작성하려면 로그인해야 합니다.