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

문제링크 : https://www.acmicpc.net/problem/2003

2003번: 수들의 합 2

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int arr[10001];

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

    int sum = 0;
    int cnt = 0;

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

    for(int i=1; i<=N; i++)
    {
        for(int j=i; j<=N; j++)
        {
            sum+=arr[j]; //누적합
            if(sum == M) cnt++; //목표값이면 카운팅
        }
        sum = 0; //누적합 초기화
    }

    cout << cnt;

    return 0;
}

누적 합 문제이다.

누적 합에 브루트포스를 사용하거나 투포인터를 이용해 풀 수 있는데 나는 브루트포스를 이용해서 풀었다.

 

단순히 이중 반복문의 인덱스 i, j을 이용해서 각 구간을 설정해주고 구간합을 구하여 M과 같으면 카운팅해준다.

구간이 끝날때마다 sum은 0으로 초기화해줌으로써 다음 구간의 합을 구할때 이상이 없도록 해준다.