[백준 13900번] [구현] 순서쌍의 곱의 합

처음에 이 문제를 보고 자연스럽게 생각나는 풀이방법은

이중 for loop를 활용하여 계속해서 해당 결과값들을 더해나가는 것이다.

 

그런데, 그런 방식으로 풀게 될 경우

데이터가 10만개이므로 시간 복잡도가 대략 O(n^3)가 나온다.

(시그마 계산을 하게 되면 이는 쉽게 증명할 수 있다.)

그러면 최악의 경우를 고민해보았을 때 시간초과가 난다는 사실을 알 수 있다.

 

그렇기에 다른 방법을 강구해야 한다.

잘 생각해보면 결과적으로 하나의 숫자는 다른 모든 숫자와 곱해지는 형태이므로 전체 sum에서 자기 자신을 뺀 만큼이 곱해지게 되는 양상으로 진행되게 된다.(결합법칙 정도로 이해하면 충분하다.)

 

다만, 중복되는 것을 감안해서 마지막에 1/2처리만 해주면 된다.

 

일종의 대각선 갯수 구하는 알고리즘이랑 느낌이 비슷하다고 할 수 있겠다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main(void){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n;
    cin >> n;

    vector<int> sum_store;
    for(int i = 0 ; i < n; i ++){
        int temp;
        cin >> temp;
        sum_store.push_back(temp);
    }

    long long sum_value = 0;
    for(int i = 0; i < sum_store.size(); i++){
        sum_value += sum_store[i];
    }

    long long result = 0;

    for(int i = 0; i < sum_store.size(); i++){
        result += (sum_value - sum_store[i]) * sum_store[i];
    }

    cout << result / 2 << "\n";

    return 0;
}