2003번 - 수들의 합 2

2003번 - 수들의 합 2

 

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

2003번: 수들의 합 2

---

투 포인터 알고리즘의 기본적인 문제라고 할 수 있다.

 

어떻게 보면 이중 반복문을 사용하여 쉽게 풀 수도 있지만 이는 시간 초과가 날 확률이 높으므로 우린 투 포인터 알고리즘 개념을 사용할 것이다.

 

투 포인터 알고리즘 개념이 익숙치 않다면- https://yhoons.tistory.com/6 

투포인터 알고리즘(Two Pointers Algorithm) - c++

---

 

이 문제는 투포인터 알고리즘 개념을 안다면 쉽게 풀 수 있는 문제이다.

 

#include<iostream>
#define maximum 100001
using namespace std;

int main() {

    int N, M; //N:수열의 개수, M:연속적인 부분 수열의 합 조건
    int count=0, sum=0; //count: 합M을 만족하는 부분 수열의 개수, sum:합을 저장하는 변수
    int start, end; //투포인터
    int a[maximum] = {0,}; //수열을 저장하는 배열 a
    
    cin >> N >> M;

    for(int i=0; i<N; i++) {
        cin >> a[i];
    }

    start=end=0; //start와 end를 인덱스 0으로 가르키도록 초기화

    for(;end<=N;) { //end포인터가 인덱스 끝까지 도달할 때까지 반복
        
        if(sum > M) //연속적인 부분 수열 합이 요구 합 보다 클 때
            sum -= a[start++];  //start포인터가 오른쪽으로 이동하기 전 가르켰던 곳에 있는 값을 빼주고 오른쪽으로 이동
        else if(sum < M)
            sum += a[end++];
        else {
            count ++;
             sum += a[end++];
        }
    }
    cout << count;
}