tols91   3달 전

그냥 dp로 푸니까 최적부분구조가 안나와서 정렬 후 dp로 하니까 나오긴 하는데

왜 정렬하고 하면 최적부분구조가 되는지 설명해주실분있나요..?

koosaga   3달 전

평행한 두 수직선상에 남자와 여자를 늘어놓고 둘을 이어서 매칭시킨다고 생각하면

1 2 3 4

 \ \ \ \

2 3 4 5

뭐 이런 형식이 나오는데,

만약에 두 매칭이 X자 형태로 꼬여있다면 \ \로 풀어줄 수 있고, 그런다고 손해를 보는 일이 없습니다.

고로 정렬하면 최적부분구조가 나오고 dp가 가능합니다.

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