오늘 서연이는 남자친구와 함께 먹을 요리를 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가지 재료에 대한 정보가 주어질 때 두 요리의 맛 점수 차이의 최솟값을 구하여라.

#4201 upload 1 done 1 how_to_reg 1

[swat]스타트와 링크 timer 2s memory 512MB

#4201

[swat]스타트와 링크 2s 512MB