수열 백준 2559번 c++

 

수열 2559번 문제링크 

 

연속된 k개의 합을 구하되, 최대 합을 답으로 내는 문제다.

항상 k개여야 하니까, 시작 인덱스 0, 끝 인덱스 k-1 의 합으로 시작한다.

길이가 일정한 누적합이기 때문에, 시작 인덱스와 끝 인덱스만 바뀐다. 투포인터 문제다. 

 

k= 3 이라면,  아래 처럼 인덱스가 일정하게 증가한다. 

시작0 ~ 끝2,  시작1 ~ 끝3, 시작2 ~ 끝4

현재 시작인덱스의 값을 빼주고, 현재 끝인덱스 +1 의 값을 더해주면 된다. 

 

 

"맞았습니다"코드 링크 

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

int n, k, start_idx, end_idx;
long long sum, sum_temp;

int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);

  cin >> n >> k;
  vector<int> v(n); 
  for(int i = 0; i < n; i++) cin >> v[i]; // 입력받기 끝 

  // 인덱스 0부터 k-1까지 k개의 합 
  for(int i = 0; i < k; i++) sum_temp += v[i];
  start_idx = 0, end_idx = k-1; 

  sum = sum_temp;
  
  while(end_idx < n){ 
    sum_temp -= v[start_idx++]; // 현재 인덱스 값 빼기, 인덱스 증가
    if(end_idx + 1 == n) break;
    sum_temp += v[++end_idx];   // 인덱스 증가시킨 후 그 인덱스 값 더하기
    sum = max(sum_temp, sum);
  }
  cout << sum;
  return 0;
}