[백준 2559번 / C++ ] 수열

누적합 문제이다. 

start 포인트와 end 포인트를 둬서 투포인트로 풀어도 된다. 하지만 이 방법은 여기서 최적의 풀이법은 아니다.

#include <iostream>
#include <algorithm>
#include <climits>
#include <vector>
using namespace std;
int answer = INT_MIN;
int main() {
	int start, end, n, k, sum = 0;
	cin >> n >> k; 
	start = 0;
	end = k - 1;
	vector <int> v(n); 
	for (int i = 0; i < n; i++)cin >> v[i]; 
	for (int i = 0; i <= k - 1; i++)sum += v[i]; 
	for (int i = 0; i <= n - k; i++) {
		answer = max(answer, sum); 
		if (end == n - 1)break; 
		else {	
			sum -= v[start++]; 
			sum += v[++end]; 
		}
	}
	cout << answer; 
}

<투포인트 코드>

 

이런식으로 포인트 두개를 계속 바꿔주면서 sum 값을 비교하는 코드를 짤수 있다. 하지만 두개의 포인트 말고 하나의 포인트로도 구현 할 수 있다.

 

즉, 입력값을 다 더한 누적합 배열을 하나 생성하여 (현재 인덱스의 누적합) - ((현재 인덱스-K) 의 누적합)으로  풀면된다. 

#include <iostream>
#include <algorithm>
#include <climits>
#include <vector>
using namespace std;
int answer = INT_MIN;
int temp, sum[100001],n,k; 
int main() {
	cin >> n >> k; 
	for (int i = 1; i <= n; i++) {
		cin >> temp; 
		sum[i] = sum[i - 1] + temp; 
	}
	for (int i = k; i <= n; i++) {
		answer = max(answer, sum[i] - sum[i - k]);
	}
	cout << answer; 	
}