검은점과 하얀점 연결

2n개의 점이 x축의 좌표 1,2,...2n에 놓여 있다. 그 중 n개는 검은 점이고, n개는 하얀 점이다. 하나의 검은 점과 하나의 하얀 점을 연결하여 한 쌍을 만들면, 모두 n개의 쌍이 만들어진다. 한 쌍의 점을 연결할 때는, 왼쪽 점에서 출발하여 수직으로 올라가고, 거기서 수평으로 오른쪽으로 간 후, 다시 수직으로 내려가서 연결하면 하나의 길이 생긴다. 이렇게 생긴 n개의 길들은 서로 겹쳐서는 안되고, 서로 교차해서도 안 된다. 모든 길의 거리의 합을 가장 작게 하도록 n개의 길을 만드는 프로그램을 작성하시오. 단, 거리의 단위는 수직, 수평 모두 1이다.

        그림 1
        그림 2

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

※ 이 문제의 채점 데이터는 공개된 공식 데이터가 없어 재구성한 것입니다. 문제 지문은 원본(정보올림피아드 기출)을 따릅니다.

첫째 줄에는 점의 개수를 나타내는 정수 2n이 주어진다. 2n은 100이하의 정수이다. 그 다음 줄에는 n개의 0과 n개의 1로 이루어진 문자열이 주어진다. 0은 하얀 점이고, 1은 검은 점이다. 왼쪽부터 차례로 좌표 1,2,...2n에 해당한다.

첫째 줄에는 길의 거리의 합을 출력한다. 다음 n개의 줄의 각 줄에는 연결되는 한 쌍의 점들의 좌표를 나타내는 두 정수를 출력한다. 두 정수 사이에는 빈칸이 하나 있다. 앞의 정수가 뒤 정수보다 작아야하고, n개의 줄은 앞 정수가 커지는 순서로 출력한다.

생성자가 기록되지 않았습니다.

출처 올림피아드 > 한국정보올림피아드 > KOI 1999 > 2차 대회 > 고등부 2번