[BOJ] 2559번 | 수열 (C++)

🔗문제 보러가기

2559번: 수열

 

🧑‍💻풀이 과정

네트워크에서 TCP 프로토콜을 공부할 때 봤었던 슬라이딩 윈도우(Sliding window) 개념을 적용하여 풀 수 있습니다.

1. 입력으로 주어지는 각 숫자들을 배열(arr)에 저장하되, [0, K - 1]까지의 합계를 별도의 변수(sum)에 저장해둡니다.
2. int start = 0, last = K로 인덱스 변수를 둡니다.
3. 정답 변수(maxSum)을 1번에서 구한 sum 변수 값으로 초기화합니다.
4. last < K가 만족할 때, 다음 과정을 반복합니다.
   • sum -= arr[start++];
   • sum += arr[last++];
   • maxSum = max(maxSum, sum);

 

✏️소스 코드 및 결과

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

int main()
{
	ios::sync_with_stdio(false);
	cout.tie(NULL); cin.tie(NULL);

	int N, K;
	cin >> N >> K;

	// 1. [0, K - 1]까지 합계 구하기
	int sum = 0;
	vector<int> sequence(N);
	for (int i = 0; i < N; i++)
	{
		cin >> sequence[i];

		if (i < K)
			sum += sequence[i];
	}

	// 2. start, last 인덱스를 통해, 한 칸씩 전진
	int maxSum = sum;
	for (int start = 0, last = K; last < N; start++, last++)
	{
		sum -= sequence[start];
		sum += sequence[last];

		maxSum = max(maxSum, sum);
	}

	cout << maxSum;
	return 0;
}