백준 순서쌍의 곱의 합 13900 PYTHON

 

 

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

import itertools
import sys
input = sys.stdin.readline
n = int(input())
answer = list(input().split())
check = []
for i in range(len(answer)):
    answer[i] = int(answer[i])
combination = list(itertools.combinations(answer,2))
for i in range(len(combination)):
    check.append(combination[i][0] * combination[i][1])
print(sum(check))

처음 문제를 보고 2가지 경우만 고려하면 되니, 조합을 생각하였다. 하지만 조합으로 문제를 풀게 된다면, 시간초과가 나오게된다.

메모리 초과 오류를 해결하기 위해 규칙을 찾아보기로 했다.

ex) n = 5  1,2,3,4,5가 입력이라면, 어떤식으로 조합이 되나 고려했다.

(1,2),(1,3),(1,4),(1,5)

(2,3),(2,4),(2,5)

(3,4),(3,5)

(4,5) 

경우의 수는 이정도로 나올것이다.

그럼 위의 식에서 규칙을 찾아보면 1*(2+3+4+5) + 2*(3+4+5) + 3*(4+5) + 4*(5) 이런 규칙이 나온다.

그래서 위의 입력값을 모두 더한뒤,초기값을 빼주고 곱해주는것을 반복해주면 된다.

import sys
input = sys.stdin.readline
n = int(input())
answer = list(map(int, input().split()))
sum_answer = sum(answer)
result = 0
for i in range(len(answer)):
    sum_answer -= answer[i]
    result += sum_answer * answer[i]
print(result)