[백준 13900번] 순서쌍의 곱의 합 (C++)

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

13900번: 순서쌍의 곱의 합

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

ll arr[100001];
ll sum = 0;

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);
    
    int N;
    cin >> N;

    ll result = 0;

    for(int i=1; i<=N; i++)
    {
        cin >> arr[i];
        sum+=arr[i]; //누적합
    }

    for(int i=1; i<=N; i++)
    {
        result += (sum-arr[i]) * arr[i]; //자기 자신 제외 곱해지는 값
        sum-=arr[i]; //계산한 값 지우기
    }

    cout << result; 

    return 0;
}

누적합 문제이다.

계산함에 따라서 수의 범위가 커져서 관련된 변수를 long long으로 선언해야 한다.

 

처음에 누적합을 구해놓고, 이 합에서 자기 자신을 빼고 곱해준 값을 결과값에 더해준다.

(현재값을 기준으로 나머지 값들과 전부 곱해주고 더해주기 때문에 더해주고 곱해줘도 된다.)

이렇게 계산한 대상 값을 누적합 부분에서 지워줘야 중복값이 발생하지 않는다.