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

문제링크

 

문제

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을 시작 지점으로 잡고 배열에 저장된 값을 더해나간다. 이 때 M과 같다면 경우의 수가 존재하는 것이고, M보다 크다면 배열의 다음은 확인할 필요가 없다. 어차피 M보다 크기 때문에 M과 같아질 수 없기 때문이다.

시작 지점을 N까지 올려가며 확인을 반복하면 된다.

코드

#include <iostream>
using namespace std;
 
int n, m, cnt;
int arr[10001];
 
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    cin >> n >> m;
 
    for (int i = 1; i <= n; i++) {
        cin >> arr[i];
    }
 
 
    int st = 1;    // 시작 지점
    while (st <= n) {
        int sum = 0;
        for (int i = st; i <= n; i++) {
            sum = sum + arr[i];
 
            // 합이 m과 같으면 경우의 수 +1
            if (sum == m) {
                cnt++;
                break;
            }
 
            // 합이 m보다 크다면 그냥 종료
            if (sum > m) {
                break;
            }
        }
 
        st++;
    }
    cout << cnt;
 }