[백준 1806] 부분합

문제

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

알고리즘

두 포인터

풀이

부분합이 $S$ 이상일 때 구간의 최소 길이를 구하는 문제입니다.

합이 $S$ 이상인 구간들은 포인터를 맨 처음부터 오른쪽으로 이동시키면 구할 수 있습니다. 문제가 어렵다기 보단 깔끔한 구현에 초점을 맞춰 코드를 보면 좋을 것 같습니다

코드

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < n; ++i)
#define REP(i, n) for (int i = 1; i <= n; ++i)
using namespace std;

signed main() {
#ifndef ONLINE_JUDGE
    freopen("in", "r", stdin);
    freopen("out", "w", stdout);
#endif
    cin.tie(NULL);
    cout.tie(NULL);
    ios::sync_with_stdio(false);

    int N, S;
    cin >> N >> S;
    vector<int> vt(N);
    for (auto& x : vt) {
        cin >> x;
    }
    int l = 0, r = -1, psum = 0, ans = INT_MAX;
    while (r < N) {
        if (psum >= S) {
            ans = min(r - l + 1, ans);
            psum -= vt[l++];
        } else {
            psum += vt[++r];
        }
    }
    cout << (ans == INT_MAX ? 0 : ans);
    return 0;
}