[백준/Python] 13900번: 순서쌍의 곱의 합

문제

 

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

---

풀이

해당 문제는 누적합을 활용해서 풀 수 있다.
모든 경우의 수는 조합으로, nC2이다. 따라서, 시간이 부족하다.
단순 곱을 더하기만 하면 되는 경우이기에 분배 법칙과 누적 합을 활용하면 된다.
예를 들어, [1,2,3,4]인 경우 1*(2+3+4) + 2*(3+4) + 3*(4) 로 계산할 수 있는 것이다.
따라서, 괄호 안의 합은 누적합을 활용하면 된다.
아래 코드는 앞에서부터 계산한 누적합을 활용하기 위해, 분배법칙을 뒤에서부터 시행했다.

 

코드

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

dp = [0]*(N+1)
for i in range(N-1):
    dp[i+1] = dp[i]+nums[i]

result = 0
for i in range(N-1, 0, -1):
    result += nums[i]*dp[i]

print(result)