[백준 1806번] 부분합

문제 링크: https://www.acmicpc.net/problem/1806

1806번: 부분합

<문제 풀이> 투 포인터

투 포인터 알고리즘을 적용하면 된다.

 

left, right 포인터를 준비하고 찾은 부분합이 s이상이면 그때의 수열의 길이와 이전에 구했던 길이의 최솟값으로 갱신하고 left을 증가시키면 된다. 왜냐하면 부분합이 s이상인걸 찾았을 때 right을 증가시키면 수열의 길이가 증가하므로 확인할 필요가 없다.

 

<C++ 소스 코드>

#include <iostream>
#include <algorithm>
using namespace std;
 
int n, s;
int arr[100000];
int main(void) {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> n >> s;
    for (int i = 0; i < n; i++) cin >> arr[i];
    int l = 0, r = 0, sum = 0, res = n;
    bool existence = false;
    while (true) {
        if (sum >= s && s) {
            existence = true;
            res = min(res, r - l);
            sum -= arr[l++];
        }
        else if (r == n) break;
        else sum += arr[r++];
    }
    if (existence) cout << res;
    else cout << 0;
    return 0;
}