合併スライム

ソース:白駿#14241
タイムアウトメモリ制限2秒512 MB

質問する

英善と孝彬は水晶の泥を合わせるゲームをしている.二人は水晶泥を二つ選んで一つにしなければならない.ゲームはまだスライムが1つ残っている間に終わります.
すべての水晶泥には正数の大きさがある.2つのスライムxとyを加算すると,合成したスライムの大きさはx+yであった.また、スライムを加えるたびに、二人はx*y点を得る.
英善と孝彬が得られる点数の最値を求めるプログラムを作成してください.

入力

第1行は斜線の個数N(2≦N≦100)を与える.
2行目はスライムの大きさを示した.サイズが100以下の自然数.

しゅつりょく

1行目は英善と孝彬が得られる点数の最値を印刷した.

I/O例

入力例1

2 3 4

サンプル出力1

12

入力例2

3 2 2 2

サンプル出力2

12

入力例3

3 1 2 3

サンプル出力3

11

入力例4

3 3 1 2

サンプル出力4

11

に答える

説明する

2つの

スライムのサイズを抽出し、乗算した値をスコアに追加し、乗算した値を配列に入れ、同じ手順を繰り返します.

python code

# 백준 14241번
from sys import stdin
from collections import deque

def slime(n, slimes):
    slimes.sort(reverse=True)   # 큰 순서대로 정렬하기

    deq = deque()
    for i in range(n):
        deq.append(slimes[i])

    result = 0  # 얻는 점수

    while (len(deq) > 1):
        x = deq.popleft()
        y = deq.popleft()
        result += x*y   # 곱한 만큼 점수로 추가
        deq.appendleft(x+y) # 합친 슬라임은 다시 deq에 집어넣기

    return result   # 점수 반환

n = int(stdin.readline())
slimes = list(map(int, stdin.readline().split()))

result = slime(n, slimes)
print(result)