[BOJ 1806] 부분합 C++

난이도: Gold 2
번호: 1806
생성일: March 3, 2023 6:05 PM
알고리즘 분류: 누적 합, 두 포인터
언어: C++

1806번: 부분합

C++

#include <iostream>
#include <algorithm>

using namespace std;

int main(void)
{
    // 입력 받기
    int N, S;
    cin >> N >> S;

    // 배열 입력 받기
    int arr[N];
    for (int i = 0; i < N; i++)
        cin >> arr[i];

    // 투 포인터 알고리즘 사용
    int start = 0, end = 0, sum = 0, minLen = N + 1;
    // start와 end 포인터를 이용하여 배열을 한 번만 순회
    while (end < N)
    {
        // end 포인터를 증가시키며 합계 구하기
        sum += arr[end++];
        // sum이 S보다 크거나 같아진 경우
        while (sum >= S)
        {
            // 최소 길이 갱신
            minLen = min(minLen, end - start);
            // start 포인터 증가시키며 합계에서 제외
            sum -= arr[start++];
        }
    }

    // 부분 배열을 찾지 못한 경우
    if (minLen == N + 1)
        cout << 0 << "\n";
    // 부분 배열을 찾은 경우
    else
        cout << minLen << "\n";

    return 0;
}