#include<stdio.h>
#include<vector>
using namespace std;
int main(){
int n,k;
scanf("%d %d", &n, &k);
vector<int> temp(n);
for(int i = 0; i < n; i++)
scanf("%d", &temp[i]);
int start = 0;
int end = k-1;
int maxSum = 0;
for(int i = start; i <= end; i++)
maxSum += temp[i];
int result = maxSum;
while(end < n){
start++;
end++;
maxSum -= temp[start-1];
maxSum += temp[end];
if(maxSum > result)
result = maxSum;
}
printf("%d", result);
return 0;
}1. 투포인터 알고리즘을 사용했다.
https://www.youtube.com/watch?v=iSjvuixMPmQ
어떤 특정 조건을 만족하는 연속 구간을 구할 때 O(N) 으로 풀 수 있도록 도와주는 알고리즘
int start = 0;
int end = k-1;
int k = 2;
start ↓ end ↓
| 3 | -2 | -4 | -9 | 0 | 3 | 7 | 13 | 8 |
int sum = temp[start] + temp[end] = temp[0] + temp[1] = 3 + (-2) = 1
두 포인터를 각각 오른쪽으로 한 칸씩 이동한다.
start++;
end++;
start ↓ end ↓
| 3 | -2 | -4 | -9 | 0 | 3 | 7 | 13 | 8 |
!! 여기서 중요한 점 !!
-2와 -4를 더하는 것이 아니라, 기존의 3을 빼고 새로 만난 -4를 더한다.
sum -= temp[start-1];
sum += temp[end];
--> 계산 전 sum은 3 + (-2) 이다. (-2)를 이미 더했기 때문에 다시 계산할 필요없이 3 + (-2) - 3 + (-4)를 하는 것이다.
이게 구간이 2라서 더 복잡한 계산을 하는 것처럼 보일 수 있다. 구간이 2일 때는 그냥 (-2) + (-4) 하는 것이 더 빠르기 때문이다. 그러나 구간이 10000이라고 생각해보자. 계산을 10000번씩 해야되는 것을 단 2번만에 끝낼 수 있다.
첫 점수 : 40점
