[ALOG] 백준 13900 - 순서쌍의 곱의 합

문제

N개의 정수 중 서로 다른 위치의 두 수를 뽑는 모든 경우의 두 수의 곱의 합을 구하라.

예를 들어 N = 3이고 주어진 정수가 2, 3, 4일 때, 두 수를 뽑는 모든 경우는 (2, 3), (2, 4), (3, 4)이며 이때 각각의 곱은 6, 8, 12이다. 따라서 총합은 26이다.

출력

코드

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    int count;    cin >> count;
    vector<int> numberList(count);

    for (int input, i = 0; i < count; ++i)
    {
        cin >> input;
        numberList[i] = input;
    }

    long long int sum = 0;
    long long int result = 0;

    for (int i = count - 1; i > 0; --i)
    {
        sum += numberList[i];
        result += sum * numberList[i - 1];
    }

    cout << result;

    return 0;
}

결론

그냥 생각하면 O(N^2)로 생각하기 쉽지만, 좀 더 고민해보면,
분배법칙을 사용해서 O(N)시간에 가능하다.