2n개의 점이 x축의 좌표 1,2,...2n에 놓여 있다. 그 중 n개는 검은 점이고, n개는 하얀 점이다.

하나의 검은 점과 하나의 하얀 점을 연결하여 한 쌍을 만들면, 모두 n개의 쌍이 만들어진다.

한 쌍의 점을 연결할 때는, 왼쪽 점에서 출발하여 수직으로 올라가고,

거기서 수평으로 오른쪽으로 간 후, 다시 수직으로 내려가서 연결하면 하나의 길이 생긴다.

이렇게 생긴 n개의 길들은 서로 겹쳐서는 안되고, 서로 교차해서도 안된다.

모든 길의 거리의 합을 가장 작게 하도록 n개의 길을 만드는 프로그램을 작성하시오.

단, 거리의 단위는 수직, 수평 모두 1이다.

그림 1의 경우 다른 방법으로 연결할 수도 있지만, 위 방법이 최소 연결 방법이고 거리의 합이 31이다.

그림 2의 경우도 다른 방법이 있지만, 위 방법이 최소 연결이며 거리의 합은 40이다.

검은점과 하얀점 연결 timer 1초 memory 64MB

검은점과 하얀점 연결 1초 64MB