[2003] 수들의 합 2

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

2003번: 수들의 합 2

<문제>

최대 10000개의 배열에서 1초안에 투포인터로 합이 m인 경우의수를 세어야한다.

은근히 투포인터랑 비슷한 '느낌'의 알고리즘도 많다.

 

슬라이딩 윈도우는 len = right-left+1이 항상 일정한 투포인터,

혹은 항상 left++과 right++을 동시에 진행하는 알고리즘이고

토끼와 거북이 알고리즘도 어떻게보면 left와 right의 속도가 다른, 투포인터라고 할 수 있겠다.

 

 

right을 감소시키는 경우는 없으므로, 구현할때 항상 left를 증가시키는 부분을 먼저 검사해준다.

연산횟수는 left와 right이 각각 N번, 총 2N으로, 시간복잡도는 O(N)

<소스코드>

#include<bits/stdc++.h>
using namespace std;
int n, m, a[10001], l, r;
int main(void) {
    int i;
    scanf("%d %d", &n, &m);
    for (i = 0; i < n; i++)
        scanf("%d", &a[i]);
    int sum = 0, cnt = 0;
    l = 0;
    r = 0;//투포인터, 왼쪽에서 시작
    while (l <= r && r <= n) {
        if (sum >= m) {
            if (sum == m)cnt++;//정답 카운트
            sum -= a[l++];
        }
        else {//left++ -> right++
            if (r == n)break;
            sum += a[r++];
        }
    }
    printf("%d", cnt);
    return 0;
}