[Baekjoon] 2559번: 수열

 

 

 

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

2559번: 수열

 

---

 

문제 해결 과정

착안

$n$ 번째 숫자 $a_n$ 부터 $(n+K-1)$ 번째 숫자 $a_{n+K-1}$ 까지 연속된 $K$ 개의 숫자를 더한 값을 $S_n$ 이라고 하면, 

$$S_{n+1} = S_n + a_{n+K} - a_n \quad(n \geq 1,\space 2 \leq K \leq N)$$

이므로, 이전 단계의 합의 값을 알면 숫자 두 개만 더하고 뺌으로써 다음 번째의 연속합을 계산할 수 있으므로 $K$ 개의 연속된 숫자의 합을 구하는 시간 복잡도를 동적계획법(dynamic programming)을 통해 낮추고자 하였다.

 

구현

[스포 주의] 아래 '더보기'를 누르면 코드가 나오니 주의하세요~

#include <iostream>

using namespace std;

int Degrees[100000];

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

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

	for (int i = 0; i < N; i++)
		cin >> Degrees[i];

	int sum = 0;
	for (int i = 0; i < K; i++)
		sum += Degrees[i];

	int max = sum;
	for (int i = 1; i <= N - K; i++)
	{
		sum += Degrees[K + i - 1] - Degrees[i - 1];
		if (sum > max)
			max = sum;
	}

	cout << max << "\n";
	return 0;
}

 

실행 결과