[BOJ / C++] 1806 부분합

문제링크

문제
10,000 이하의 자연수로 이루어진 길이 N짜리 수열이 주어진다. 이 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 프로그램을 작성하시오.

입력
첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다.

출력
첫째 줄에 구하고자 하는 최소의 길이를 출력한다. 만일 그러한 합을 만드는 것이 불가능하다면 0을 출력하면 된다.

예제 입력 1
10 15
5 1 3 5 10 7 4 9 2 8
예제 출력 1
2

문제 정리

연속된 수들의 합이 입력받은 수를 넘으면서 길이가 최소가 되야한다. 크거나 같은 값 중 최소 이분탐색과 투 포인터로 풀 수 있다. 여기서는 투 포인터로 풀어보겠다. 투 포인터 알고리즘

1. st와 en이 배열의 시작을 가르킨다
2. st부터 en까지의 합이 S이상이 될 때까지 en을 증가시킨다.
3. st부터 en까지의 거리를 구하고 거리의 최솟값을 갱신한다.
4. 구한 합에서 st가 가르키는 배열의 값을 뺀 뒤 st를 1 증가시킨다.
5. en이 배열의 크기를 벗어나기 전까지 2,3,4번을 반복한다.

구현 코드

#include <bits/stdc++.h>
using namespace std;

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

    int arr[100001];

    int n,s;
    cin >> n >> s;
    for(int i=0; i<n; i++)
        cin >> arr[i];
    
    int result = 100001;

    int sum = arr[0];
    int en = 0;
    
    for(int st=0; st<n; st++)
    {
    	//합이 S이상이 될 때까지 en을 증가시킨다.
        while(sum < s && en < n)
        {    
            en++;
            sum+=arr[en];
        }
		//이 배열의 크기를 넘어서면 반복문 종료
        if(en==n)
            break;
        
        result=min(result, en-st+1);
		
        //st를 이동시키기 전에 현재 st가 위치한 배열의 값을 합에서 빼준다
        sum = sum - arr[st];
        
    }
    //합이 S이상이 되는 경우가 없으면 0출력
    if(result == 100001)
        result = 0;
    cout << result;

}