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

[ BOJ ] 14929번 : 귀찮아 (SIB)

문제 :  https://www.acmicpc.net/problem/14929

14929번: 귀찮아 (SIB)

---

[  문제  ]

[  입력  ]

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

---

[  문제 접근 및 풀이  ]

$$ x_1x_2 + x_1x_3 + x_2x_3 = x_1(x_2+x_3) + x_2x_3 $$

왼쪽의 식처럼 각각의 항들을 직접 2중 for문으로 구하게 된다면 \(O(n^2)\)으로 

n의 크기가 최대 10만으로 시간초과가 뜰 수 있다.

따라서 오른쪽 식처럼 누적합을 이용하여

\(x_i\)일 때  \(psum_n\)에서 \(psum_i\)를 빼주고 \(x_i\)를 곱한 후

\(1\)~\(n\) 항까지 더해주면 \(O(n)\)에 풀이가 가능하다.

[  소스 코드  1  ]

\(O(n^2)\) 풀이

2중 for문

#include<bits/stdc++.h>
using namespace std;
int arr[100001],N;
long long sum;
void input();
void solve();
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	input();
	solve();
}
void input(){
    cin >> N;
    for(int i=0;i<N;i++) cin >> arr[i];
}            
void solve(){
    for(int i=0;i<N;i++){
        for(int j=i+1;j<N;j++){
            sum+=arr[i]*arr[j];
        }
    }
    cout << sum;
}

위 코드는 왼쪽 식처럼 모든 항을 직접 구했을 때 코드이다.

BOJ에 제출하였을 때 역시 시간 초과가 났었다.

2중 for문으로 풀었을 경우 TL

[  소스 코드  2  ]

\(O(n)\) 풀이

누적합

#include<bits/stdc++.h>
using namespace std;
int arr[100001],psum[100001],N;
long long sum;
void input();
void solve();
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	input();
	solve();
}
void input(){
    cin >> N;
    for(int i=1;i<=N;i++) {
    	cin >> arr[i];
        psum[i]=psum[i-1]+arr[i];
    }
}            
void solve(){
    for(int i=1;i<N;i++){
        sum+=arr[i]*(psum[N]-psum[i]);
    }
    cout << sum;
}

---