천천히 더하기

N 개의 숫자 배열이 주어지면 하나의 숫자만 남을 때까지 다음 작업을 반복합니다. 두 숫자를 선택하고 그 두 숫자의 합계로 바꿉니다. 선택된 숫자의 합은 벌점이 되고 전체 벌점의 합계를 구합니다.

예를 들어 [1, 2, 3, 4, 5] 배열이 주어지면 첫번째 2와 3을 선택할 수 있습니다. 그러면 배열은 [1, 5, 4, 5]로 변환되고 5의 벌점이 발생합니다. 이 문제의 목표는 주어진 입력에 대해 가능한 최대의 벌점을 찾는 것입니다.

예제 1

입력

arr = [4, 2, 1, 3]  

출력

26
// 4와 3을 선택하여 7의 벌금이 발생하고
// 배열은 [7, 2, 1]로 바뀝니다.
// 7과 2를 선택하여 9의 벌금이 발생하고
// 배열은 [9, 1]로 바뀝니다.
// 9와 1을 선택하여 10의 벌금이 추가되고
// 벌금의 총합계는 26 입니다.