[백준] 13900번 순서쌍의 곱의 합 ★★

💡문제접근

• N개의 정수 중 두 수를 뽑아 곱한 수들의 합을 구하는 간단한 문제다.
• 하지만 N의 범위는 2 ≤ N ≤ 100,000이고 입력받는 정수들의 범위는 0이상 10,000이하이다. 일반적인 조합(combination)을 이용하게 된다면 시간초과가 발생한다. 뭔가 다른 규칙이 있을 것이라고 생각했다.
• 수를 나열해보니 규칙을 발견할 수 있었다.

💡테스트케이스

입력

3
2 3 4

출력

26

설명

• ((2 + 3 + 4) - 2) × 2 = 14
• ((3 + 4) - 3) × 3 = 12
  따라서, 정답은 26이다.

💡코드(메모리 : 41824KB, 시간 : 76ms)

N = int(input())
li = list(map(int, input().split()))

result = sum(li)
total = 0
for i in li:
    result -= i
    total += result * i
print(total)

💡시간초과 발생한 코드

from itertools import combinations

N = int(input())
li = list(map(int, input().split()))

total = 0
for i in combinations(li, 2):
    result = 1
    for j in range(len(i)):
        result *= i[j]
    total += result
print(total)

💡소요시간 : 18m