결합법칙을 이용해 풀면 간단히 풀리는 문제다.
주어진 정수가 a,b,c라고 하면 정답은
a*b + a*c + a*d +
b*c + b*d +
c*d
이므로, 결합법칙을 이용하면
a*(b+c+d) +
b*(c+d) +
c*(d)
로 표현될 수 있다. 이를 이용하면 O(N)의 시간 복잡도로 문제를 해결할 수 있다.
#include <iostream>
using namespace std;
int main()
{
int N;
int input[100001];
cin>>N;
for(int i=0;i<N;i++)
cin>>input[i];
long long int result=0;
long long int sum = 0;
for(int i=N-2;i>=0;i--)
{
sum += input[i+1];
result += input[i]*sum;
}
cout<<result<<endl;
return 0;
}