[c++] 2003번: 수들의 합 2

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

2003번: 수들의 합 2

 

문제 요약

 

A[1]~A[N] 수열에서 i~j번째 수(부분 수열)의 합이 M이 되는 경우의 수를 구하라.

 

 

범위

 

N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000),  A[x] ≤ 30,000 (자연수)

 

 

---

 

부분수열의 범위를 정해서 합을 계산하면 되는데 부분수열의 합의 범위는 L ~ R 로 정했는데

L의 범위는 1~N, R의 범위는 0~N으로 해서 

L로 부분수열의 첫번째 원소를 가리키고 각 원소들을 합을 구하면서 R의 값을 증가시켰다. 

이때, while문을 통해 R의 범위를 제한하고 만약 부분수열의 합(sum)이 m 값보다 작다는 조건을 달아서 연산이 진행되도록 했다.

 

여기서 sum != m 이 아닌 sum < m 을 조건으로 했는데, 그 이유는

만약 sum != m 을 조건으로 한다면 sum이 m을 무조건 지나가면서 증가하는 것이 아니라 바로 m의 값을 초과할 수 있기 때문이다. 초과하게 되면 어쨌든 sum == m이 아니기 때문에 while문의 조건에 맞기 때문에 그대로 진행된다. 이렇게 되면 안되기 때문에 sum < m 으로 했다.

 

//2003번: 수들의 합 2
#include <iostream>
#include <algorithm>
using namespace std;
int n, m, A[10001];

void input(){
    cin >> n >> m;
    for(int i=1; i<=n; i++) cin >> A[i];
}

void solution(){
    int sum = 0, R = 0, cnt = 0;
    for(int L=1; L<=n; L++){
        sum -= A[L-1];
        while(R+1<=n && sum < m){
            sum += A[++R];
        }
        if(sum == m) cnt++;
    }
    cout << cnt << '\n';
}

int main() {
    ios::sync_with_stdio(0); cout.tie(0); cin.tie(0);
    input();
    solution();
    return 0;
}

 

 

 

 

 

💡공부 및 기록용 블로그이므로 오류가 있을 수 있습니다.💡

만약 문제에 오류나 오타가 있다면 댓글로 알려주세요➿
언제나 환영합니다. 감사합니다. 화이팅!