inchworm 알고리즘

inchworm 알고리즘이란?

inchworm은 자벌레를 말하는데 inchworm 알고리즘은 자벌레가 기어가는 모양과 같이 선두와 마지막에 변화를 가하면서 조건을 만족하는 구간을 찾는 알고리즘이다.

머리와 꼬리가 이동하는 개념으로 투포인트와 같은 개념이다.

 

이 알고리즘은 프로그래밍 콘테스트에 자주 출제 되는 유형으로 다음과 같은 문제가 있다.

예제 문제(출처 POJ 3061)

각각 10000보다 작거나 같은 N개의 양의 정수(10 < N < 100 000)의 시퀀스와 양의 정수 S(S < 100 000 000)가 제공됩니다. 수열의 연속 요소 중 부분 수열의 최소 길이를 구하는 프로그램을 작성하세요. 그 합은 S보다 크거나 같습니다. 입력 첫 번째 줄은 테스트 케이스의 수입니다.  각 테스트 케이스에 대해 프로그램은 첫 번째 줄에서 간격으로 구분된 숫자 N과 S를 읽어야 합니다.  시퀀스 번호는 테스트 케이스의 두 번째 줄에 간격으로 구분되어 제공됩니다.  입력은 파일 끝에서 종료됩니다. 출력 각 경우에 대해 프로그램은 출력 파일의 별도 줄에 결과를 출력해야 합니다. 해가  없으면 0을 출력합니다.

입력

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

출력

2
3

 

예제에서

5 1 3 5 10 7 4 9 2 8

합이 15 보다 커져야 하므로 

머리를 계속 이동 시키면서 합이 15보다 클 때 까지 이동시킨다. 

5 + 1 + 3 + 5 + 10 까지 더하면 24가 된다.

그 다음 꼬리 부분을 줄여 가면서 15보다 작을 때까지 이동한다.

-5 -1 -3 -5 까지 이동하면 합은 10만 남는다.

또 머리를 이동하면서 +7 을 하면 17이 되고

다시 꼬리를 이동하면서 -10 을 하면 합이 7이 되고

다시 머리를 이동하면서 +4 +9 는 합이 20이 되고

다시 꼬리를 이동하면서 -7 을 하면 13이 되고

다시 머리를 이동하면서 +2 를 해서 15가 되고

이렇게 머리와 꼬리를 계속 이동시키면서 가장 짧은 구간을 찾아 주면 된다.

 

 

 

샘플 코드

#include<bits/stdc++.h>
using namespace std;
vector<int> ans;
int main() {
    int T;
    cin>> T;
    while(T--) {
        int n,m;
        cin >> n >> m;
        ans.clear();
        for(int i=0;i<n;++i) {
            int num;
            cin >> num;
            ans.push_back(num);
        }
        int s=0,t=0,sum=0,res=n+1;
        for(;;) {
            while(t<n&&sum<m) sum+=ans[t++];
            if(sum<m) break;
            res=min(res,t-s);
            sum-=ans[s++];
        }
        if(res>n) res=0;
        printf("%d\n",res);
    }
    return 0;
}