백준 2003 수들의 합 2 C++

문제설명

 

 

 

예제 입력 및 출력

 

 

=> 투포인터의 기본개념을 묻는 문제입니다. 

 

=> while문을 통해 시간 복잡도 O(N)의 속도를 이끌어낼 수 있는 알고리즘입니다. 

 

https://codingham.tistory.com/232

백준 1806 - 부분합

위 문제는 투포인터를 활용한 문제입니다. 

해당 문제를 푼 후에 해당 문제를 풀어보는 것도 좋은 방법입니다. 

 

=> arr[0] 부문에 값을 미리 넣어 계속 틀렸었습니다. 

 

#include <iostream>
#include <algorithm>


using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    int arr[10001];
    int N,M;
    
    cin >> N >> M;
    
    for(int i=0; i<N; i++)
    {
        cin >> arr[i];
    }
    
    int start=0, end=0,cnt =0;
    int sum = arr[0];
    while(start <= end && end < N )
    {
        if (sum < M) // 아직 부분합이 S를 만족하지 못하는 경우
        {
            sum += arr[++end];
        }
        else if ( sum == M)//원하는 값을 찾았을 경우
        {
            cnt++;
            sum += arr[++end];
        }
        else if ( sum > M)//원하는 값보다 큰 경우
        {
            sum -= arr[start++];
            if(start > end)
            {
                end = start;
                sum = arr[start];
            }
        }
    }
    cout <<cnt<<'\n';
    return 0;
}

 

 

출력화면