[規格]13900-シーケンスペアの積の和(Python)

質問リンク

アルゴリズム#アルゴリズム#

数学

に答える

from itertools import combinations


N = int(input())
nums = list(map(int, input().split()))
combis = list(combinations(nums, 2))

res = sum(map(lambda x: x[0] * x[1], combis))

print(res)

最初は組み合わせで解きました.
整数の個数の範囲は(2≦N≦100000)であるため、メモリが超過している.
別の方法で問題を解決しました
(1,2,3,4,5)が与えられると,答えは以下のように求めることができる.

これは分配法則を利用してこのように変えることができる.1(2+3+4+5) + 2(3+4+5) + 3(4+5) + 4(5)また、このルールを使用するアルゴリズムは以下のとおりです.

(1+2+3+4+5)を変数に加算します.

1の変数から最初の数値1を減算します.では残り(2+3+4+5)です.

から減算された数値1と(2+3+4+5)を乗算した値を、結果値を含む変数に追加します.

(2+3+4+5)を含む変数では、1から次の値2を減算します.

3と4を繰り返します.

コードで以下のように実現する.

コード#コード#

N = int(input())
nums = list(map(int, input().split())) # N개의 숫자를 저장

sum_nums = sum(nums) # 먼저 숫자를 다 더한다.
res = 0

for n in nums: # 이제 숫자를 하나씩 빼오면서 위의 2,3,4번을 반복한다.
    sum_nums -= n
    res += sum_nums * n

print(res)