[n13900] 순서쌍의 곱의 합 in python

https://www.acmicpc.net/problem/13900

13900번: 순서쌍의 곱의 합

---

1. 메모리초과 -> 조합 함수 사용

# from itertools import permutations, combinations
#
# num = int(input())
# inp = list(map(int, input().split()))
# for i in inp:
#     arr=list(combinations(i,2))
# arrs = list(combinations(inp, 2))
# result = 0
#
# for arr in arrs:
#     x, y = arr
#     result += x * y
#
# print(result)
# -> 메모리초과

---

2. 시간 초과 -> 이중 for문

# -> 시간초과
# import sys
#
# num = int(sys.stdin.readline())
# inp = list(map(int, sys.stdin.readline().rstrip().split()))
# result = 0
#
# for i in range(num - 1):
#     for j in range(i + 1, num):
#         result += inp[i] * inp[j]
# print(result)

---

3. 결합 법칙 사용 (내림차순)

import sys

num = int(sys.stdin.readline())
inp = list(map(int, sys.stdin.readline().rstrip().split()))
result = 0
subsum = sum(inp)

for i in inp:
    subsum-=i
    result+=subsum*i

print(result)

---

4. 결합 법칙 사용 (오름차순)

 ** 총합 먼저 구해놓기 ** 

 

(ex)

4 

1 2 3 4

 

subsum=10

i=1 

subsum=10-1=9

result+=9*1 = 9

 

i=2

subsum=9-2=7

result+=7*2=9+14=23

 

i=3

subsum=7-3=4

result+=4*3=23+12=35

 

i=4

subsum=4-4=0

result+=4*0=35

 

print(result) => 35!

import sys

num = int(sys.stdin.readline())
inp = list(map(int, sys.stdin.readline().rstrip().split()))
result = 0
subsum = 0

for i in inp:
    result += subsum * i
    subsum += i

print(result)