BOJ_14929 : 귀찮아 (SIB) (C++)

풀이 방법

 

n 이 10만까지 나올 수 있으므로 이중 for 문으로 접근하면 시간 초과가 나온다.

 

주어진 식을 구현하는 문제인데, 식을 이해해보면

 

x1x2 + x1x3 + x2x3

= x1(x2+x3) + x2(x3)

= x1(x2~xN까지의 합) + x2(x3~xN까지의 합)

 

x1x2 + x1x3 + x1x4 + x2x3 + x2x4 + x3x4

= x1(x2+x3+x4) + x2(x3+x4) + x3(x4)

= x1(x2~xN까지의 합) + x2(x3~xN까지의 합) + x3(x3~xN까지의 합)

 

이렇게 표현할 수 있으며 규칙을 볼 수 있다.

 

즉, 누적합(prefix sum)을 사용하여 풀이하면 된다.

 

주의할 점은 int 형으로 값을 저장하면 안되고 long long 형으로 저장하여야 한다.

(int로 저장하면 20%에서 틀렸습니다를 볼 수 있다.)

 

 

코드

 

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cmath>
#include <cstring>
#include <stack>
#include <queue>
#include <limits.h>
#include <regex>
#include <sstream>
#include <tuple>
using namespace std;

int main() {

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    // 단순한 수학식 구현 문제
    // 곱의 누적합

    // -2 + 3 - 6 = -5

    // 두 개씩 곱하고 다 더함

    // n이 10만까지 나올 수 있으므로 시간 초과 유의

    // x1x2 + x1x3 + x2x3
    // = x1(x2+x3) + x2x3

    int n;
    cin >> n;

    vector <long long> arr(n+1);
    vector <long long> ps(n+1); // 누적합 prefix sum 사용

    for(int i = 1; i <= n; i++){
        cin >> arr[i];
        ps[i] = ps[i-1] + arr[i];
    }

    long long ans = 0;

    for(int i = 2; i <= n; i++){
        ans += arr[i] * ps[i-1];
    }

    cout << ans << "\n";

    return 0;
}