greentea31's Note

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

풀이 과정

i번째 수부터 j번째 수까지의 합 A[i] + A[i+1] + … + A[j-1] + A[j]가 M이 되는 경우의 수를 구하면 된다.

for문 중첩시키고 모든 연속구간을 만들어 보는 방법으로는 시간제한 내로 문제를 해결할 수 없다. 간단하게만 생각해봐도 N이 만까지 들어오는데 O(N^2) 알고리즘만 되도 TLE가 날 가능성이 있다. 투 포인터 알고리즘을 사용하면 O(N)으로 해결할 수 있다.

l, h 두 개의 포인터를 조절해가며 문제를 해결하였다.

소스 코드

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M, sum, number, answer, l, h;
    sum = 0; l = 0; h = 0; answer = 0;
    vector<int> vec(N);
    cin >> N >> M;

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

    while(true) {
        if (sum >= M) {
            sum -= vec[l++];
        } else if (h == N) {
            break;
        } else {
            sum += vec[h++];
        }

        if (sum == M) {
            answer++;
        }
    }
    cout << answer;
    return 0;
}