[투 포인터] BOJ 2003번 수들의 합2

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

2003번: 수들의 합 2

- 문제파악

수열의 개수 N과 자연수 M 그리고 N개의 수열이 주어진다. 수열의 연속합이 M이 되는 경우의 수를 출력하라

 

- 정답

투 포인터를 활용한다.

시작 포인터로 부터 종료 포인터까지의 합이 M보다 크거나 같을 때까지 종료 포인터를 증가 시킨다.

만약 M과 연속합이 같으면 경우의 수를 증가시키고

아니면 연속합에서 시작포인터의 요소를 빼고, 시작 포인터를 증가시킨다.

 

위 방법을 반복해서

시작 포인터가 수열 끝이면 경우의 수를 출력 한다.

 

#include "bits/stdc++.h"

using namespace std;

int arr[10001];

int main()
{
    int n,m;
    cin>>n>>m;
    
    for(int i = 0 ; i < n ; i++)
        cin>>arr[i];
    
    int ed = 0;
    long long lsum = 0;
    int nCnt = 0;
    for(int i = 0 ; i < n ; i++)
    {
        while(ed < n && lsum < m)
        {
            lsum += arr[ed];
            ed++;
        }
        
        if(lsum == m)
            nCnt++;
        
        lsum -= arr[i];
        
    }
    
    cout<<nCnt;
    
    
}