[BOJ] 1806번: 부분합

문제 링크:

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

접근법:

부분합을 prefix sum으로 O(N)으로 구해주고
투포인터로 부분합이 S이상이 되는 구간을 O(N)으로 구해주면된다.
나는 부분합이 S가 되는 구간을 구하는 건 줄 알고 계속 틀렸다 ㅠㅠ

코드:

#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second

typedef long long ll;
typedef pair<int, int> P;
typedef pair<int, pair<int, int>> P2;

int N, S, a[100001], p_sum[100001], s = 1, e = 1;

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> N >> S;
    for(int i = 1; i <= N; i++){
        cin >> a[i];
        p_sum[i] = p_sum[i - 1] + a[i];
    }
    int ans = 2e9;
    while(s <= N && e <= N){
        int val = p_sum[e] - p_sum[s - 1];
        if(val < S){
            e++;
        }else if(val >= S){
            ans = min(ans, e - s + 1);
            if(s < e)
                s++;
            else
                break;
        }
    }
    if(ans == 2e9)
        cout << 0;
    else
        cout << ans;
    return 0;
}