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

1 2 3 4

 \ \ \ \

2 3 4 5

뭐 이런 형식이 나오는데,

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

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