처음에는 단순하게 Brute Force로 풀었다.

• 배열을 입력 받는다.
• for문을 이중으로 사용하여 바깥 for문은 i=0부터 i=n-1까지, 안쪽 for문은 j=i+1부터 j=n까지 반복시킨다.
• arr[i]*arr[j]의 값을 sum에 더한다.

이렇게 풀었을 때 시간 초과가 났다. (예상한 결과였다.)

n=4, arr={1,2,3,4}일 때를 생각해보았다.
sum=(1x2)+(1x3)+(1x4)+(2x3)+(2x4)+(3x4)를 정리해보면
sum=1x(2+3+4)+2x(3+4)+3x(4)가 되는 것을 알 수 있다.
구글링 결과 이러한 형식의 문제는 부분합으로 푸는 것이 좋다는 것을 알게 되었다.

Code

#include <iostream>
#define MAX 100001
using namespace std;

int n;
long long arr[MAX];
long long psum[MAX];
long long sum=0;

void Input(){
    cin>>n;
    for(int i=0; i<n; i++){
        cin>>arr[i];
        if(i==0){
            psum[i]=arr[i];
        }
        else{
            psum[i]=psum[i-1]+arr[i];
        }
    }
}

long long Solution(){
    for(int i=0; i<n-1; i++){
        sum+=arr[i]*(psum[n-1]-psum[i]);
    }
    return sum;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    Input();
    cout<<Solution();
    return 0;
}

부분합을 사용하여 다시 풀었을 때 수의 범위를 제대로 확인하지 않고 배열을 int형으로 선언해서 오답처리 되었다.
문제를 풀기 전에 항상 수의 범위를 확인하도록 연습해야겠다.