문제 2003.수들의 합 2 (대학생 심화반 1번)

문제설명

N개의 수로 된 수열 A가 있다.

이 수열의 i번째 부터 j번째 까지의 수를 더했을 때 M이 되는 경우의 수를 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 N, M이 차례로 주어진다. (단, N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000))

둘째 줄에는 N개의 수가 차례로 주어진다. 주어지는 수는 30000이하의 자연수이다.

 

입력 예제

4 2
1 1 1 1

 

Tips

1. 구하고자 하는 수들의 합은 연속적인 수들의 합이다. 주어진 수열 A에 있는 모든 수들을 조합하여 M이 되는 경우를 구하는 게 아니다.
2. 수열의 수들이 자연수이기 때문에 부분 수열에 수를 추가하면 항상 값이 증가한다. 따라서, i 번째로 시작하는 부분 수열에서 수의 합이 M이라면 그 뒤로 수를 추가해도 수의 합은 M이 절대 될 수 없다. 즉, 임의의 위치에서 시작한 부분 수열의 수들의 합이 M이 되는 경우는 0개 또는 1개이다.
3. 배열의 최대 크기는 10,000이므로 2중 for문(O(n^2))을 돌려도 10^4 * 10^4 = 10^8 이므로, 제한 시간 0.5초에 걸리지 않는다. (10^9 = 1초 기준)

정답 코드

#include <bits/stdc++.h>

#define fastio cin.tie(0)->sync_with_stdio(0)

using namespace std;

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

    vector<int> v1(N);

    // input data
    for(int i = 0; i < N; i++){
        cin >> v1[i];
    }

    int cnt = 0;
    for(int i = 0; i < N; i++){
        int sum = 0;
        for(int j = i; j < N; j++){
            sum += v1[j];
            if(sum == M){
                //cout << j << '\n';
                cnt++;
                break;
            }
        }
    }
    
    int ans = cnt;

    cout << ans << '\n';
}