BOJ - 2559. 수열 (C++)

2559. 누적합 (prefix sum)

https://www.acmicpc.net/problem/2559

2559번: 수열

[풀이]
누적합을 이용한 풀이를 생각해내지 못하면 시간초과를 받게되는 문제이다. 나 또한 그랬다.
 
첫 번째 코드는 누적합 없이 푼 코드이다. → 시간초과
참고로 accumulate()는 O(N)이며 해당 코드의 시간복잡도는 O(N^2)이다.

#include <bits/stdc++.h>
using namespace std;
vector<int> input;
int N, K, in, maximum;

int main(){
	ios::sync_with_stdio(0); cin.tie(0);	
	cin >> N >> K;
	for (int i=0; i<N; i++) {
		cin >> in;
		input.push_back(in);
	}
	for (int i=0; i<N-K+1; i++){
		int sum = accumulate(input.begin()+i, input.begin()+i+K, 0);
		if (maximum <= sum) maximum = sum;	
	}
	cout << maximum;	
}

 
두 번째 코드는 누적합을 사용해 풀어본 코드이다. → 맞았습니다

#include <bits/stdc++.h>
using namespace std;
int psum[100004];
int N, K, in, maximum=-1e9;

int main(){
	ios::sync_with_stdio(0); cin.tie(0);	
	cin >> N >> K;
	for (int i=1; i<=N; i++) {
		cin >> in;
		psum[i] = psum[i-1] + in;
	}
	for (int i=K; i<=N; i++){
		if (maximum <= psum[i]-psum[i-K]) maximum = psum[i]-psum[i-K];
	}
	cout << maximum;	
}