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

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

 

풀이

출력값은 x1 * x2 + x1 * x3 + ... x1 * xn + x2 * x3 + x2 * x4 + ...x2 * xn ... x(n-1) * xn 이므로

정리해서 x1(x2 + x3 + ... xn) + x2(x3 + x4 + ... xn) 와 같이 표현할 수 있다

이때 xi부터 xn까지 하나하나 더하는 과정을 n번 반복하면 시간초과가 되기 때문에 누적합을 이용한다

 

제출 코드

#include <iostream>
using namespace std;

int arr[100001];
int ps[100001];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n;
    cin >> n >> arr[0];
    ps[0] = arr[0];
    for (int i = 1; i < n; i++)
    {
        cin >> arr[i];
        ps[i] = ps[i - 1] + arr[i];
    }

    long long sum = 0;
    for (int i = 0; i < n - 1; i++)
        sum += arr[i] * (ps[n - 1] - ps[i]);

    cout << sum;
}