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

Problem

---

Solution

---

N과 M을 입력 받고 N개의 정수로 이루어진 수열 A를 입력 받는다. 누적 합 배열인 prefixSum을 초기화 하고 두 개의 반복문을 사용해 모든 부분합을 구한다. 첫 번째 반복문에서는 구간의 시작 위치 start를 1부터 N까지 순회한다. 두 번째 반복문에서는 구간의 끝 위치 end를 start부터 N까지 순회한다. 모든 가능한 구간 합을 확인한 후 누적 합 배열을 이용하여 구간 합을 계산 한다. prefixSum[end] - prefixSum[start - 1]을 통해 수열 A의 start부터 end까지의 합을 구하고 이 합이 M과 같다면 경우의 수를 증가시킨다. 모든 구간에 대해 경우의 수를 구하고 이를 출력한다.

Answer

---

#include <iostream>
#include <vector>

using namespace std;

int main() {
    ios_base::sync_with_stdio(0);cin.tie(0);
    int N, M;
    cin >> N >> M;

    vector<int> A(N + 1, 0);
    vector<int> prefixSum(N + 1, 0);

    for (int i = 1; i <= N; ++i) {
        cin >> A[i];
        prefixSum[i] = prefixSum[i - 1] + A[i];
    }

    int count = 0;

    for (int start = 1; start <= N; ++start) {
        for (int end = start; end <= N; ++end) {
            int sum = prefixSum[end] - prefixSum[start - 1];
            if (sum == M) {
                count++;
            }
        }
    }

    cout << count << endl;

    return 0;
}

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