[🥈4 / 백준 13900 / 파이썬] 순서쌍의 곱의 합

 

13900번: 순서쌍의 곱의 합

 

문제

N개의 정수 중 서로 다른 위치의 두 수를 뽑는 모든 경우의 두 수의 곱의 합을 구하라.

예를 들어 N = 3이고 주어진 정수가 2, 3, 4일 때, 두 수를 뽑는 모든 경우는 (2, 3), (2, 4), (3, 4)이며 이때 각각의 곱은 6, 8, 12이다. 따라서 총합은 26이다.

입력

첫 번째 줄에는 입력 받을 정수의 개수 N(2 ≤ N ≤ 100,000)

두 번째 줄에는 N 개의 정수가 주어진다. 이때 입력 받는 정수들의 범위는 0이상 10,000 이하이다.

출력

모든 경우의 곱의 합을 출력한다.

 

예제 입력 1 3 2 3 4	예제 출력 1 26
예제 입력 2 4 1 2 3 4	예제 출력 2 35
예제 입력 3 4 2 3 2 4	예제 출력 3 44

 

풀이

 

모든 쌍의 곱의 합을 구해야 한다.

단, 정수의 최대 개수가 100,000로, 정말 모든 쌍을 구한다면 2^100,000의 연산이 필요하다.

당연히 시간 초과가 발생할 것이므로 다른 방법을 모색해야 한다.

 

예제 2번을 살펴보도록 하자.

1부터 시작하여 모든 순서쌍을 구한다면 다음과 같은 방법을 이용하게 될 것이다.

 

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

(2, 3), (2, 4)

(3, 4)

 

이들의 곱을 구하여 모두 더해야 한다. 그리고 여기서 규칙을 찾을 수 있다.

위의 순서쌍을 조금 다른 방식으로 보자.

 

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

            (2, 3), (2, 4)

                        (3, 4)

 

위와 같이, 앞에서부터 더한 것을 묶어서 바로 뒤의 것과 곱해준 뒤, 총 합에 더하면 된다.

이를 식으로 표현하면 다음과 같다.

 

1*2 + (1+2)*3 + (1+2+3)*4

 

n = int(input())
arr = list(map(int,input().split()))[::-1]

summ,result = arr.pop(),0
while arr:
    cur_num = arr.pop()
    result += summ*cur_num
    summ += cur_num
print(result)