[백준/Python] #23827 수열(Easy)

문제

알고리즘

해당 배열의 모든 정수쌍의 곱의 합을 구하는 문제이다. 배열이 500000개가 최대이므로 반복문 2개를 사용하면 시간초과가 나오게 된다.

이때, 누적합을 사용해주면 된다. 1<= i < j <= n에서 A[i] * A[j]의 합을 구하는 것이므로  A[i]를 하나 정해주고 누적합을 통해 미리 계산해 놓은 (A[i+1] + ... + A[n]) 값을 더해서 누적시켜주면 모든 순서쌍의 합이 되므로 이를 계산만 해주면 된다.

그러면 누적합을 먼저 계산해주고, 반복문을 통해 i를 설정해준다음에 누적합계산을 통해 (A[i+1] + ... + A[n])을 찾고 곱해주면 된다.

코드

import sys
input = sys.stdin.readline

n = int(input())
arr = list(map(int,input().split()))
prefix = [0]*(n+1)
for i in range(1,n+1):
    prefix[i] = prefix[i-1] + arr[i-1]

ans = 0
for i in range(1,n):
    ans = (ans + arr[i-1] * (prefix[n] - prefix[i]))%1000000007
print(ans)