2559번 - 수열 | 슬라이딩 윈도우 알고리즘 (C++)

---

문제

---

풀이

슬라이딩 윈도우 알고리즘을 이용해 풀이했다.

 

  1. 0부터 k-1까지는 모두 sum에 더한다. 이때, 최대가 되는 합을 저장할 answer에 sum의 값을 넣는다.

	for (int i = 0; i < k; i++) {
		sum += arr[i];
	}

	answer = sum;

 

 

  2. k부터 n-1까지는 arr[i]는 sum에 더하고, arr[i - k]는 sum에서 뺀다. answer과 sum 중 최댓값을 answer에 저장한다.

 

	for (int i = k; i < n; i++) {
		sum += arr[i];
		sum -= arr[i - k];
		answer = max(answer, sum);
	}

 

---

코드

#include <iostream>
#include <algorithm>
using namespace std;

int arr[100001];

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int n, k, sum = 0, answer = 0;

	cin >> n >> k;

	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}

	for (int i = 0; i < k; i++) {
		sum += arr[i];
	}

	answer = sum;

	for (int i = k; i < n; i++) {
		sum += arr[i];
		sum -= arr[i - k];
		answer = max(answer, sum);
	}

	cout << answer;

	return 0;
}

 

---

결과