[C/C++] 백준 #2003 수들의 합 2(두개의 포인터)

두개의 포인터는 연속된 구간을 나타낼 수 있는 두개의 인덱스를 유지하면서, 그 구간의 결과가 해가 되는지 검사하는 방법입니다.  현재 영역에서 영역이 커지면 결과도 커져야 하고, 영역이 작아지면 결과도 작아져야 합니다.  이 조건을 만족하지 않으면, 사실상 두개의 포인터를 이용할 경우가 별로 없습니다.

 

two pointers

 

양수들의 구간의 합은 위의 조건에 부합합니다.  [a .. b] 구간에서 구간이 하나 증가하면, 구간의 합은 늘어나게 됩니다.  또한 구간이 하나 줄어들면, 구간의 합은 줄어들게 됩니다.  이를 이용해서 연속된 구간의 합이 M이 되는 곳을 찾을 수 있습니다.  시간 복잡도는 \(O(N)\)입니다.

 

제가 작성한 소스입니다.

//------------------------------------------------
//    baekjoon #2003
//        - by Aubrey Choi
//        - created at 2019-09-28
//------------------------------------------------
#include <stdio.h>

int main()
{
    int n, m, a[10001], i, j, ans=0;
    scanf("%d%d",&n,&m);
    for(i=0;i<n;i++) scanf("%d",a+i);
    i=j=0; m-=a[0];
    while(j<n)
    {
        if(m==0) { ans++, m+=a[i++]-a[++j]; }
        else if(m<0) m+=a[i++];
        else m-=a[++j];
    }
    printf("%d\n", ans);
}