[C++] 23827 - 수열(Easy)

문제링크 : https://www.acmicpc.net/problem/23827

23827번: 수열 (Easy)

티어 : 실버4

 

문제를 보자마자 $N$이 50만이라서 포기할 뻔 했지만 생각만 해보면 쉬운 문제이다.

예제의 입력을 보면,

1 2 3, 이는 $1(2+3) + 2(3)$을 구하라는 것을 의미하며 이를 누적합을 이용하여 풀 수 있다.

이를 수식으로 정리해보자.

 

---

sum[i] : 0부터 i번째 인덱스까지의 수열의 합

---

 

반복문을 사용하여 

$arr[i] * (sum[N-1] - sum[i])$를 구하여 문제조건에 맞게 출력하면 된다.

ll arr[500005];
ll sum[500005];
int main() {
    fastio();
    int N;
    cin >> N;
    for(int i=0; i<N; i++) {
        cin >> arr[i];
    }
    sum[0] = arr[0];
    ll res=0;
    for(int i=1; i<N; i++) {
        sum[i] = sum[i-1] + arr[i];
    }
    for(int i=0; i<N; i++) {
        res = (res + (arr[i] * (sum[N-1] - sum[i]) % D7)) % D7;
    }
    cout << res;
}