[백준] 2003번 수들의 합 2 (C++)

문제

N개의 수로 된 수열 A[1], A[2], …, A[N] 이 있다. 이 수열의 i번째 수부터 j번째 수까지의 합 A[i] + A[i+1] + … + A[j-1] + A[j]가 M이 되는 경우의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다.
다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다.
각각의 A[x]는 30,000을 넘지 않는 자연수이다.

예제 입력 1

4 2
1 1 1 1

예제 입력 2

10 5
1 2 3 4 2 5 3 1 1 2

출력

첫째 줄에 경우의 수를 출력한다.

예제 출력 1

3

예제 출력 2

3

풀이

문제 해결 방법

이 문제는 두 포인터 알고리즘을 사용하여 해결할 수 있습니다. 주요 해결 단계는 다음과 같습니다:

1. 두 포인터 초기화: 시작점(L)과 끝점(R)을 배열의 시작 위치에 둡니다.
2. 구간 합 계산: 현재 구간의 합을 유지하면서 포인터를 이동합니다.
3. 포인터 이동:
   • 구간 합이 M보다 작으면 R을 오른쪽으로 이동
   • 구간 합이 M보다 크면 L을 오른쪽으로 이동
   • 구간 합이 M과 같으면 카운트 증가

이 알고리즘의 시간 복잡도는 O(N)입니다.

코드

#include <iostream>
#include <vector>

using namespace std;

int n, m, N;
int sum = 0;
int cnt = 0;
int L = 0, R = 0;

int main() {

    //N과 M 입력받기
    cin >> n >> m;

    //배열 입력 받기
    vector<int> A(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> A[i];
    }

    while (R <= n) {
        sum += A[R++];
        while (sum > m) { // sum이 m보다 커졌을 때, 작거나 같아질 때가지 L을 증가시켜서 값을 뺀다.
            sum -= A[L++];
        }
        if (sum == m) cnt++;
    }
    cout << cnt;
    return 0;
}