시간 제한 메모리 제한 제출 횟수 정답 횟수 (비율) 정답자 수
1.0 초 32 MB 1 1 (100%) 1
문제
과학자들은 화성에 이상한 세균을 발견했고 현재 연구를 진행하고 있다. 그들이 알려주기를 하나의 세균으로부터 시작해 세균은 두개의 새 세균으로 분리되며 (그 과정에서 죽는다), 세균의 숫자는 2의 거듭제곱의 형태이다. 그러므로, 첫번째 세대의 세균은 하나만 있게 된다. 이것은 두개의 두번째 세대의 세균으로 분리되고, 네개의 세번째 세대의 세균으로 분리되고, 계속 진행된다 - 결국 2K개의 세균이 K+1세대에 나타나게 된다. 다음과 같은 방법으로 이 세균들에게 번호를 붙인다 : * K세대에 각 세균의 자손들은 다음과 같은 번호를 갖는다: {1,2}, {3,4}, {5,6}, ... , {2K-1, 2K} * K-1세대의 각 세균의 자손들은 다음과 같은 번호를 갖는다: {1,2,3,4}, {5,6,7,8}, ..., {2K-3, 2K-2, 2K-1, 2K} * K-3세대의 각 세균의 자손들은 다음과 같은 번호를 갖는다: {1,2,3,4,5,6,7,8}, ..., {2K-7, 2K-6, 2K-5, 2K-4, 2K-3, 2K-2, 2K-1, 2K} * ... * 2번째 세대의 두개의 세균은 다음과 같은 자손들을 갖는다: {1,2,...,2K-1)과 {2^K-1+1, 2^K-1+2, ..., 2K} 중괄호 안의 숫자집합은 한 세균으로부터 나온 자손들의 집합이다. 말하자면, 현재세대의 2K개의 세균은 어떤 옛 세균으로부터 나온 자손들의 번호는 연속적인 번호를 갖는다는 것이다. 알아야 할 것은 옛 세균의 자손들은 연속적인 번호를 갖는다는 조건을 만족하는 경우가 여러 순열이 존재한다는 것이다. 과학자들은 세균들을 순서대로 배치할 때 이러한 순열들이 최소 가능 길이를 갖도록 하고 싶다. 세균 순서 배치의 길이란 이웃한 세균 쌍의 거리의 총합이다. 특히, 여기에는 정량화할 수 있는 반발이 두 세균사이에 있어서, 만약 그들이 세균 순서 배치에서 서로 바로 다음에 나타날 경우의 최소거리이다. (바로 인접한 이웃을 제외한 나머지에서는 반발은 일어나지 않는다.) 모든 세균쌍의 반발값이 주어질 때, 위의 조건들을 만족한 세균 순서 배치(순열)의 최소 가능 길이를 구하여라.
입력
첫번째 줄에 문제에서 설명한 자연수 K(1<=K<=9)가 주어진다. 각 2K줄에는 2K개의 [0, 106]범위내의 정수가 주어진다. 2K * 2K 숫자는 각 세균쌍의 반발값을 나타낸다. m번째 줄에 n번째 열은 세균 m과 n의 반발값을 나타낸다. 당연히, 이것은 n번째 줄에 m번째 열의 숫자와 같다. m=n일 경우 반발값은 0이다.
출력
첫번째 줄에 단 하나의 줄로 조건들을 만족하는 가능한 세균 순서 배치의 최소 거리를 출력한다.
힌트
입력예제1 ``` 2 0 7 2 1 7 0 4 3 2 4 0 5 1 3 5 0 ``` 출력예제1 ``` 13 ``` 입력예제2 ``` 3 0 2 6 3 4 7 1 3 2 0 7 10 9 1 3 6 6 7 0 3 5 6 5 5 3 10 3 0 9 8 9 7 4 9 5 9 0 9 8 4 7 1 6 8 9 0 8 7 1 3 5 9 8 8 0 10 3 6 5 7 4 7 10 0 ``` 출력예제2 ``` 32 ```