[백준/C++] 2003번 : 수들의 합 2

 

 

 

 

풀이

• 누적합과 투포인터를 이용한다.
• 왼쪽 포인터와 오른쪽 포인터를 설정하여 구간의 합을 계산한다. 
• 구간의 합이 M과 같으면 경우의 수를 증가시키고 M보다 작으면 오른쪽 포인터를 증가시켜 구간을 확장하고 구간 합이 M보다 크면 왼쪽 포인터를 증가시켜 구간을 축소시킨다.
• 오른쪽 포인터가 끝에 도달할 때까지 반복한다.
• 시간복잡도 O(N)

 

 

 

코드

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int N, M;
    cin >> N >> M;

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

    int count = 0; 
    int left = 0;  
    int right = 0; 
    int sum = A[0];

    while (right < N) {
        if (sum == M) {
            count++;
            sum += A[++right];
        } else if (sum < M) {
            sum += A[++right];
        } else {
            sum -= A[left++];
        }
    }

    cout << count << endl;

    return 0;
}

 

 

 

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

2003번: 수들의 합 2