[PS] 백준 2003번: 수들의 합 2

|

문제

내가 이해한 문제 내용

연속된 수열의 합이 $M$이 되는 경우의 수를 구하시오.

접근 방식

어느 정도 시간을 들이면 생각할 수 있는 알고리즘이지만 시간이 없었기 때문에 빠르게 공부해서 풀었다. 투 포인터, 말 그대로 2개의 포인터를 놓고 시작과 끝을 증가시키면서 부분합으로 $M$인지 판단하는 알고리즘이다.

어려웠던 점 & 배운 점

수원을 안 갔다왔으면…생각할 시간이 좀 더 있었을 것 같은데 아쉽다.

시간복잡도

$O(N)$

코드

#include <cstdio>

int n,m,s,e,ans;
int a[10001];

int main(void)
{
    scanf("%d%d",&n,&m);
    for(int i=1; i<=n; i++){
        scanf("%d",&a[i]);
    }

    for(int i=2; i<=n; i++){
        a[i] += a[i-1];
    }

    e = 1;
    while(e<=n){
        if(a[e]-a[s]<m) e++;
        else if(a[e]-a[s]>=m){
            if(a[e]-a[s]==m) ans++;
            s++;
        }
    }

    printf("%d",ans);
    return 0;
}