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

문제

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

접근 방법

N이 100,000이기에 곱셈을 하나씩 해주면 시간 초과가 발생합니다.
곱셈의 횟수를 줄일 수 있어야 합니다.

코드

#include <iostream>
using namespace std;

int N;
int nums[100001];
long long prefixSums[100001];
long long answer;

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

    for (int i = 1; i <= N; ++i)
    {
        cin >> nums[i];
        prefixSums[i] = prefixSums[i - 1] + nums[i];
    }

    for (int i = 1; i <= N; ++i)
    {
        answer += nums[i] * prefixSums[i - 1];
    }

    cout << answer;
    return 0;
}

풀이

곱하는 것이 같다면 묶어낼 수 있기에 묶어냅니다.
묶어낸 수가 연속된 수이기에 누적 합을 활용하여 구할 수 있는 것을 알 수 있습니다.