수열 (feat. 백준, 2559번)

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

2559번: 수열

 

반응형

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
using namespace std;
int main() {
	ios::sync_with_stdio(false), cin.tie(NULL);
	register int N, K, dp[100002] = { 0 }, ans = -static_cast<int>(1e9);
	register short arr[100001] = { 0 };
	cin >> N >> K;
	for (register int i = 1; i <= N; ++i)
		cin >> arr[i];
	dp[N] = arr[N];
	for (register int i = N - 1; i >= 1; --i)
		dp[i] = dp[i + 1] + arr[i];
	for (register int i = 1; i <= N - K + 1; ++i)
		ans = max(ans, dp[i] - dp[i + K]);
	cout << ans << "\n";
	return 0;
}
// *&)*@*

1. [1,2,3,4] 라는 값이 주어졌다고 할때, 각 인덱스부터 끝까지의 합은 [10,9,7,4] 입니다.
2. 만약 K=2라고 한다면, [1,2]의 합을 구해야 합니다. 이는 [10,9,7,4] 중 10 - 7 과 같습니다. 마찬가지로 [2,3]의 합은 9-4와 같습니다.
3. 따라서 입력값에 대한 누적합을 구하고 이를 P라고 한다면, P = P[i] - P[i + K + 1] 이라는 점화식이 도출됩니다.