백준 2559 c++

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

2559번: 수열

 

#include <bits/stdc++.h>

using namespace std;

int n, k,temp;	//숫자, 연속일
int psum[100001];
int ret = -10000004;	//최악의경우 : -100*10만번(n)

/*
* (-) 이중포문 : 100,000 * 100,000 ->시간초과
* 
* 해결 : 
* 구간쿼리는 psum!!!!!!!!!
* ex)
* 배열 :  1 2 3 4 5
* psum :  1 3 6 10 15
* 
* for문은 i=k~n으로 돌리면됨.
* ret=max(ret,p[i]-p[i-k])
* ex) psum[3]-psum[3-3]
*/
int main()
{
	cin >> n >> k;

	/*
	* a배열에 넣을필요없음. 바로temp로 덧셈
	* 
	*/
	for (int i = 1; i <= n; ++i) {
		cin >> temp; psum[i] = psum[i - 1] + temp;
	}

	/*
	* n=5(1,2,3,4,5)
	* k=3
	* idx:   0 1 2 3 4  5(n)
	* psum : 0 1 3 6 10 15
	* 
	* i=3~5
	* psum[3]-psum[3-3]
	* psum[4]-p[4-3]
	* psum[5]-p[5-3]
	*/
	for (int i = k; i <= n; i++) {
		ret = max(ret, psum[i] - psum[i - k]);
	}
	cout << ret;

	
}

 

이해가안되면 일단 외우자.