백준 1806 부분합(c++)

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

1806번: 부분합

두 개의 포인터를 이용해서 원하는 값을 추출하는 투 포인터 알고리즘 문제 입니다.

연속된 수들의 부분합 중에서 합이 S이상이 되는 것들 중에서 수열의 최소 길이를 구해야 합니다.  

 

테스트 케이스를 예시로 설명 드리겠습니다.

10 15
5 1 3 5 10 7 4 9 2 8

start, end 변수를 두어 이를 조작하여 원하는 수열의 최소 길이를 구해야 합니다.

sum(부분합) < S(원하는 값) 이면 end 값 증가

sum(부분합) >= S(원하는 값) 이면 start 값 증가, 수열의 최소 길이 갱신

 

이러한 로직을 바탕으로 5, 10이 수열의 최소 길이가 됩니다.

 

<코드>

#include <iostream>
#include <vector>
int a[100001];
using namespace std;

int main()
{
    int n, m;
    cin >> n >> m;
    vector<int> a(n);
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }

    int i = 0, j = 0, sum = a[0], ans = 210000000;
    while (j < n)
    {
        if (sum < m)
        {
            j += 1;
            sum += a[j];
        }
        else if (sum == m)
        {
            if (j - i + 1 < ans)
            {
                ans = j - i + 1;
            }
            j+=1;
            sum += a[j];
        }
        else if (sum > m)
        {
            if (j - i + 1 < ans)
            {
                ans = j - i + 1;
            }
            sum -= a[i];
            i++;
        }
    }
    if(ans > n) ans = 0;

    cout<<ans;
}