[C++] 백준 2559 - 수열

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

2559번: 수열

<풀이>

1. 숫자 N개 중 K개의 합을 처음부터 끝까지 모두 확인해보고 최댓값을 갱신한다.

​

<해법>

1. 배열 처음~끝까지 K개의 합을 비교하는 방법

=> 투 포인터 활용한다. 부분집합1에서 부분집합2를 구할 때, 양쪽 끝 값은 변화하고 가운데 값은 변하지 않기 때문이다.

#include <iostream>
using namespace std;
 
const int MAX = 100000 + 1;
 
int arr[MAX];
long long int res;
 
int main() {
 
    int N, K;
 
    //입력
    cin >> N >> K;
 
    for (int i = 0; i < N; i++) {
        cin >> arr[i];
    }
 
    //초기 배열1 설정
    int s = 0;
    long long int sum = 0;
    for (int i = s; i < s+K; i++) {
        sum += arr[i];
    }
    res = sum;
 
    //배열 탐색
    while (true) {
        //기존 합에 앞에 부분을 뺀다
        sum -= arr[s];
        //배열의 범위를 벗어날 경우
        if (s+K >= N) {
            break;
        }
        //합에 뒷부분을 더한다
        sum += arr[s+K];
        if (sum > res) {
            res = sum;
        }
        //다음 배열 index
        s++;
    }
 
    //출력
    cout << res;
}

 

투포인터에 대해 알아볼 수 있는 문제였습니다.