[백준 14929번] 귀찮아 (SIB) (C++)

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

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int arr[100001];
int sum[100001];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;

    for(int i=0; i<n; i++)
    {
        cin >> arr[i];
        if(i==0) sum[0]=arr[0];
        else sum[i] = sum[i-1] + arr[i];
    }
    
    ll result = 0;
    for(int i=0; i<n-1; i++)
    {
        result += arr[i] * (sum[n-1] - sum[i]);
    }

    cout << result;

    return 0;
}

 

주어진 공식에 따라 식을 살펴보면 다음과 같다.

x1(x2+x3+x4+...xn) + x2(x3+x4+x5....xn) ...

 

따라서 누적합을 미리 계산해놓고, 그에 따른 값을 곱해 최종 합을 계산해서 출력해준다.