[Two Pointer] 백준 2003 - 수들의 합 2

 

 

만약 모든 경우의 수를 다 본다면 

nC2가 걸리게 되어 O(n^2)이 걸린다!

   -> 0.5초 내에 해결해야 하기 때문에 너무 오래 걸린다

 

O(N)으로 풀어보자

 

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
#define endl '\n'
#define DIV 1000000009

int N, M, a, b, ans;
// int numbers[1025][1025]; 사실상 필요가 없다
int number[10000];

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    cin>>N>>M;
    for(int i=0; i<N; i++){
        cin>>number[i];
    }
    int sum;
    while(b<N){
        sum = 0;
        for(int i=a; i<=b; i++){
            sum += number[i];
        }
        if(sum==M){
            ans++;
            b++;
        }
        else if(sum>M){
            a++;
        }
        else{
            b++;
        }
    }
    cout<<ans;
}