[백준][C++] 1806: 부분합

문제

풀이

• 2중 for문을 사용하면 시간초과가 발생한다. 두 포인터 알고리즘을 사용한다.
• start에서 end 까지의 합이 S미만이라면 end를 증가한다. 수열의 길이를 늘린다.
• S이상이라면 start를 증가시켜서 수열의 길이를 줄인다.

코드

#include <iostream>
#include <climits>

using namespace std;

int num[100'002];

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

    int N, S;
    int sum = 0;
    int answer = INT_MAX;

    cin >> N >> S;

    for (int i = 1; i <= N; ++i)
    {
        cin >> num[i];
    }

    int start = 0;
    int end = 0;
    while (start <= end && end <= N)
    {
        if (sum >= S)
        {
            answer = min(answer, end - start + 1);
        }

        // 현재 합이 더 작다면 end를 앞으로 옮겨서 길이를 늘린다.
        if (sum < S)
        {
            end++;
            sum += num[end];
        }
        // 현재 합이 더 크다면 start를 앞으로 옮겨서 길이를 줄인다. 
        else
        {
            sum -= num[start];
            start++;
        }
    }

    // answer에 변함이 없다면 0 출력
    if (answer == INT_MAX)
    {
        cout << "0";
        return 0;
    }
    cout << answer;

    return 0;
}