백준 2559 수열 (C++)

백준 2559 수열

처음 봤을 때 어 구간합인가보다! 해서 풀려고 했는데 처음 접근을 잘못했어서 틀렸던 문제이다.

구간합인거 몰랐을 때는 이중 for문 밖에 모르니 당연히 .. 시간초과로 틀렸었고..ㅎㅎ

풀이 코드

#include <bits/stdc++.h>
using namespace std;

int N, K; // N : 2 ~ 100,000
// K 1 ~ 99,999
int psum[100004];
int ret = -10000001;

int main(){

	cin >> N >> K;
	
	for(int i = 1; i <= N; i++){
		int input;
		cin >> input;
		psum[i] = psum[i - 1] + input;
	}
	
	for(int i = K; i <= N; i++){
		ret = max( ret, psum[i] - psum [i - K] );
	}
	
	cout << ret;

	return 0;
}

일단 psum 배열에 합계를 계속 누적 시켜서 저장하고
그 다음 두번째 for문에서는 연속적인 k일 간의 온도의 합 중 큰 값을 계속 갱신 시킨다.

문제의 예시 첫번째 그림을 살펴보면 이 0번째 인덱스와 1번째 인덱스를 합한 값이 1이 되는 것을 확인할 수 있는데 2일 간의 온도 합이 1이 된다.
psum 배열의 2번 인덱스에 이 값이 담겨 있으므로 psum[2] 가 곧 첫째날, 둘째날의 온도 합을 의미한다.

그리고 여기서 부터는 단순히 구간합을 누적한 것만 필요한 게 아니라 앞에 인덱스만큼 값을 빼주어야 함을 알 수 있다.

/* psum */
0 3 1 -3 -12 -12 -9 -2 11 19

psum에 현재 저장되어있는 값이 위와 같고 연속적인 2일의 합을 구한다고 할 때 2일차 + 3일차의 온도 합을 구하려면 psum[3] - psum[1] 한 값이 2일차와 3일차의 온도 합이 된다.

이 패턴을 계속 따라가다 보면 psum[4] - psum[2] … 이런 식으로 가는 것을 확인할 수 있다.

for(int i = K; i <= N; i++){
	ret = max( ret, psum[i] - psum [i - K] );
}

결국 연속적인 k일 중 가장 큰 값을 구하려면 위와 같은 코드로 작성할 수 있다.

두번째 for문 부분 N의 범위를 헷갈려서 < 를 사용했다가 틀렸었다.
처음 psum 배열에 넣을 때 <= 로 넣어놓고 < 를 사용해서 틀리다니 ㅋㅋㅎㅎ..