시작

이 문제는 이미 정해진 수열에 정해진 값의 길이 만큼 더한뒤 그 중 큰 값을 구하면 되는 것이다. 우선 막상 보면 2중for문 부터 사용할텐데 이 문제는 O(n^2)으로 해결 안되는 문제로, 무조건 O(n)으로 밖에 해결이 안되는 문제다. 그러니 알고리즘을 한번 짜보자.

알고리즘

1. 우선 0~k번째를 더한 값을 구한다.
2. 그리고 가장 큰값인지 계산한다.
3. 큰값이 아니면, 다시는 아니고, i+k번째의 값을 더하고, i번째의 값을 뺀sum값도 큰값인지 확인

이런식으로 해결 하면 O(n)의 시간복잡도를 가진 코드가 나오게 될 것이다.

코드

#include<iostream>
#include<vector>
#include<string>
#include<algorithm>

using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	int n, k, max = -214783647, sum = 0;
	cin >> n >> k;
	vector<int> numArr(n+1); 
	for (int i = 0; i < n; i++) {
		cin >> numArr[i];
	}
	
	// 우선 처음 sum값 구하기
	for (int i = 0; i < k; i++) {
		sum += numArr[i];
	}

	// n - k만큼 돌려서 out of index안뜨게 만들기
	for (int i = 0; i <= n - k; i++) {
		// 큰값 찾기
		if (sum > max) max = sum;
		// 우선 i + k를 해서 값을 만들고
		sum += numArr[i + k];
		// i번째의 값을 뺀다.
		sum -= numArr[i];
	}
	cout << max;
}