묶음 밧줄의 길이
면접 대비시간 제한2초메모리 제한1024 MB
n개 소포의 크기가 주어질 때, 두 묶음을 골라 합친 뒤 두 크기의 합만큼 로프를 쓰며, 모든 소포를 하나로 묶는 데 드는 최소 로프 길이를 구한다.
문제
온라인 쇼핑의 발달로 상품 배송과 밀접하게 연결된 물류 산업이 크게 번성하여 많은 인력이 필요하게 되었다. 이 성장하는 산업의 트럭 운전사인 Alex는 매일 창고에 흩어져 있는 여러 소포를 다른 도시로 운송하는 일을 맡았다.
고속도로를 달리는 트럭에 대한 공식 안전 규정에 따라, Alex는 모든 소포를 단단히 묶어 트럭에 안전하게 실어야 했다. Alex는 트럭에 소포를 묶는 데 필요한 끈의 길이가 소포 자체의 크기에 달려 있다는 것을 알고 있었다. 또한 n개의 소포는 n - 1번의 묶음으로 모두 묶을 수 있다. 더욱이 소포를 묶을 때 흩어지지 않도록 Alex는 한 번에 두 개의 소포만 묶을 수 있었다. 하루에 소비되는 끈의 양이 많고 Alex가 그 비용을 지불해야 했기 때문에, 그는 모든 소포를 가장 짧은 끈으로 묶기를 바랐다.
예를 들어 크기가 각각 8, 5, 14, 26인 소포 4개가 있다. Alex가 처음 두 개를 묶으면 필요한 밧줄의 길이는 13(8+5 = 13)이고 나머지 두 소포에 필요한 밧줄은 40(14 + 26 = 40)이다. Alex가 이 두 묶음을 계속 묶으면 필요한 밧줄의 길이는 53(13 + 40 = 53)이다. 따라서 4개 소포의 총 길이는 106(13 + 40 + 53 = 106)이다. Alex가 다른 방법으로 처음 두 개를 묶고(8 + 5 = 13), 세 번째 것을 더하고(13 + 14 = 27), 마지막 소포를 묶으면(27 + 26 = 53), 필요한 끈의 길이는 93(13 + 27 + 53 = 93)에 불과하다. 이제 당신의 임무는 Alex가 필요한 끈의 최소 길이를 찾도록 돕는 것이다.
입력
첫째 줄에는 테스트 케이스의 수를 나타내는 정수 T가 주어진다. 각 테스트 케이스는 두 줄로 이루어진다. 첫째 줄에는 소포의 수를 나타내는 양의 정수 n이 주어진다. 둘째 줄에는 각 소포의 크기를 나타내는 n개의 양의 정수가 공백으로 구분되어 주어진다.
출력
각 테스트 케이스마다 모든 소포를 하나로 묶는 데 필요한 밧줄의 최소 길이를 한 줄에 출력한다.
제한
- 1 ≤ T ≤ 10
- 1 ≤ n ≤ 1000
- 각 소포의 크기는 최대 1000이다.