[백준] 1806 부분합

1806번: 부분합

 

www.acmicpc.net

풀이

투 포인터 알고리즘을 사용하여 해결하였다. 이 때 합이 s보다 같거나 큰 경우에는 정답을 찾기 위해 최솟값 비교를 해주어야한다.

코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n, s;
    cin >> n >> s;
    vector<int> num(n);

    for (int& i : num)
        cin >> i;

    int start = 0, end = 0;
    int sum = 0;
    int ans = 100001;

    while (true) {
        if (sum >= s) {
            ans = min(ans, end - start);
            sum -= num[start++];
        }
        else if (end == n) break;
        else sum += num[end++];
    }
    cout << (ans == 100001 ? 0 : ans) << '\n';
    return 0;

}