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

문제

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

2559번: 수열

---

문제 요약

n개의 정수로 이루어진 수열이 있을 때, k개 연속 합이 가장 큰 값을 출력한다.

---

코드

#include <iostream>

#define MAX_N 100000

using namespace std;

int n, k;

int arr[MAX_N];

int main() {
	cin >> n >> k;
	
	// 수열 입력
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}

	// 탐색할 부분 수열의 범위 인덱스 설정
	int start = 0;
	int end = k - 1;

	// 초기 부분 수열의 연속합 설정
	int cur_sum = 0;
	for (int i = 0; i < k; i++) {
		cur_sum += arr[i];
	}

	int res = cur_sum;
	
	// 부분 수열을 오른쪽으로 한 칸씩 움직이며 연속합의 최대값 탐색
	while (end < n - 1) {
		start++;
		end++;

		cur_sum = cur_sum - arr[start - 1] + arr[end];

		res = max(res, cur_sum);
	}

	cout << res;
}

---

코드 설명

슬라이딩 윈도우 기법을 이용한다.

 

수열의 왼쪽에서부터 크기가 k인 부분 수열을 하나씩 탐색하며 연속합의 최대 값을 구한다.

 

연속합을 구할 때, 이전 부분 수열의 가장 왼쪽 값을 빼고, 이전 부분 수열 바로 다음 값을 더한다.+ 해당 부분 수열의 합을 요소를 모두 더하는 것이 아닌, 이전 부분 수열에서 양 끝값만 바꿔서 구한다.