문제
오늘 서연이는 남자친구와 함께 먹을 요리를 2가지 하려고 한다. 요리를 만들기 위한 재료는 총 N개 이며 N은 신기하게도 짝수이다. 이제 두 요리의 양을 비슷하게 하기 위해 N/2개 씩 재료를 사용하여 요리를 만들려고 한다.
이론에 충실한 서연이는 1부터 N까지 재료가 있을 때 재료의 조합에 따라 요리가 더 맛있게 느껴지는 정도를 점수로 표현한 ‘맛 점수’를 조사하였다. Sij는 i번 재료와 j번 재료를 조합했을 때 해당 요리에 추가되는 맛 점수이다. 맛 점수는 요리에 속한 모든 쌍의 능력치 Sij의 합이다. Sij는 Sji와 다를 수도 있으며, i번 재료와 j번 재료를 조합했을 때 요리에 더해지는 맛 점수는 Sij와 Sji이다.
예를 들어, 1, 2번으로 첫 번째 요리, 3, 4번으로 두 번째 요리를 하는 경우 두 요리의 맛 점수는 아래와 같다.
첫 번째: S12 + S21 = 1 + 4 = 5
두 번째: S34 + S43 = 2 + 5 = 7
두 요리의 맛 점수가 너무 차이가 나면 한 요리가 상대적으로 맛이 없게 느껴질 것을 걱정하여 두 요리의 맛 점수 차이를 최소로 하려고 한다. N가지 재료에 대한 정보가 주어질 때 두 요리의 맛 점수 차이의 최솟값을 구하여라.
입력
첫째 줄에 N(4 ≤ N ≤ 20, N은 짝수)이 주어진다.
둘째 줄부터 N개의 줄에 S가 주어진다.
각 줄은 N개의 수로 이루어져 있고, i번 줄의 j번째 수는 Sij 이다. Sii는 항상 0이고, 나머지 Sij는 1보다 크거나 같고, 100보다 작거나 같은 정수이다.
출력
두 요리의 맛 점수 차이의 최솟값을 출력한다.
예제
4
0 76 11 3
86 0 17 37
17 18 0 56
6 66 65 0
26
로그인해야 코드를 작성할 수 있어요.