[C++] 2559: 수열

실버 Ⅲ

 

#include <iostream>
using namespace std;

int tem[100000];

int main() {
	int N, K;
	scanf("%d%d", &N, &K);
	for (int i = 0; i < N; i++) {
		scanf("%d", &tem[i]);
	}

	int low = 0;
	int high = K;
	int sum = 0;
	for (int i = low; i < high; i++) {
		sum += tem[i];
	}

	int sum_ans = sum;
	while (high < N) {
		sum += tem[high++];
		sum -= tem[low++];
		if (sum > sum_ans) sum_ans = sum;
	}
	printf("%d", sum_ans);
}

 

투 포인터 문제! 인데.. 음 유형적으로는 첫번째 유형이긴 한데

머라고 하지 무조건 왼쪽 오른쪽 둘다 ++ 하면서 올라감

 

음 아마도 0~5까지 다 더한다음 1~6까지 다 더하고, 2~7까지 다 더하고...

이렇게 하면 중복계산이 많아서 시간초과가 나니까

그걸 해결하는 방법으로 투포인터를 사용한다

는게 이 문제의 핵심인듯 하다

 

그냥 투포인터 첫번째 유형보다 개념적으로는 훨씬 쉽고 이해가 잘 가는 것 같기두 하고..

음 그렇네

약간 dp적인 느낌이 나는 문제

전에 계산했던 값 쓰기! 그냥 그런 느낌

별 거 아님