[BOJ] 귀찮아 (SIB) 14929번 C++

 

 

문제

입력

n과 xi가 주어짇나. n은 10만 이하ㅇ고, xi는 젗ㄹ댓값이 100이하인 정수디이다.

출력

위에서 구하란 걸 구하면 된ㄷ.

 

접근 방식

 

3
1 -2 3

 

입력이 다음과 같을 때

 

1x-2 + 1x3 + -2x3 을 구하면된다

 

근데 최대 입력이 10만이기 때문에 이중 반복문을 사용하면 시간초과가 발생한다!!

 

그래서

x1x2 + x1x3 + x1x4 + x1x5 + ..... 는 x1(x2 + x3 + x4 + x5 ....) 임을 활용해서 문제를 풀면 된다..!

 

코드

 

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

int main() {
    int n; cin>>n;
    vector<int> x(n+1), pSum(n+1);
    for(int i=1; i<=n; i++) {
        cin>>x[i];
        pSum[i] = x[i] + pSum[i-1];
    }

    long long sum = 0;

    for(int i=2; i<=n; i++) {
        sum += x[i] * pSum[i-1];
    }

    cout<<sum;
}

 

 

수학은 어려워..!