(C++) - 백준(BOJ) 1806번 : 부분합 답

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

1806번: 부분합

two pointer 문제였습니다.

 

 

풀이방법

s보다 작거나 같을 때까지 계속해서 누적합을 구합니다.

s를 넘는 순간 l을 한칸 오른쪽으로 옮겨줍니다.

 

1.sum==s 최소의 길이인지 확인, r(right)을 더해줍니다.2.sum>s 그 뒤의 배열의 누적합을 구하는 것은 의미 없는 연산이므로 l++해줍니다.

 

Code

#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll n, a[100001], s;

ll twoPointer(){
    ll ans = n + 1;
    ll sum = a[0];
    ll l = 0, r = 0;
    while(l <= r && r < n){
        if(sum < s) sum += a[++r];
        else if(sum == s) {
            ans = min(ans, r - l + 1);
            sum += a[++r];
        }
        else{
            ans = min(ans, r - l + 1);
            sum -= a[l++];
        }
    }
    if(ans > n) return 0;
    return ans;
} 
int main(){
    cin >> n >> s;
    for(int i = 0; i < n; i++) cin >> a[i];
    cout << twoPointer();
}