[C++] 백준/Silver/14929. 귀찮아 （SIB）

문제: 귀찮아 (SIB) (백준 14929번)

문제 분석

주어진 n개의 정수에 대해, 모든 서로 다른 두 수의 곱의 합을 구하는 문제이다.
즉,

$\text{result} = \sum_{1 \leq i < j \leq n} a_i \times a_j$

직접 모든 쌍을 계산하면 O(n²) 시간 복잡도가 발생하지만, n의 범위가 클 경우 시간 초과가 날 수 있다.

해결 방법

수학적 아이디어:
두 수의 곱의 합은 다음 식으로 변형할 수 있다.

$\left(\sum_{i=1}^{n} a_i\right)^2 = \sum_{i=1}^{n} a_i^2 + 2\sum_{1 \leq i < j \leq n} a_i \times a_j$

따라서,

$\sum_{1 \leq i < j \leq n} a_i \times a_j = \frac{\left(\sum_{i=1}^{n} a_i\right)^2 - \sum_{i=1}^{n} a_i^2}{2}$

이 식을 이용하면 O(n) 시간 내에 결과를 구할 수 있다.

전체 코드

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(0); 
    cin.tie(0);
    
    int n; 
    cin >> n;
    
    vector<int> arr(n);
    long long sum = 0, square_sum = 0;
    
    // 모든 숫자를 입력받으며, 전체 합과 제곱의 합을 계산
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
        sum += arr[i];
        square_sum += 1LL * arr[i] * arr[i];
    }

    // 위의 수식을 이용하여 모든 서로 다른 두 수의 곱의 합을 계산
    long long result = (sum * sum - square_sum) / 2;
    cout << result << '\n';

    return 0;
}