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

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

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

14929번: 귀찮아 (SIB)

---

[  문제  ]

[  입력  ]

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

---

[  문제 접근 및 풀이  ]

$$x_1{x}_2+x_1{x}_3+x_2{x}_3=x_1(x_2+x_3)+x_2{x}_3$$

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

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

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

$x_i$일 때  $psu{m}_n$에서 $psu{m}_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;
}

---