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

2003번: 수들의 합

---

 

문제 )

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을 넘지 않는 자연수이다.

 

 

 

출력 :

첫째 줄에 경우의 수를 출력한다.

 

 

 

 

 

풀이)

최대 GCD문제에서 했던 것처럼 입력되는 문자열을 ' ' 기준으로 나누어 int로 변환 시킨 뒤 

 

vector로 넣어준 후 

 

투포인터를 진행해 문제를 풀어주었다.

 

 

#include <iostream>
#include <string>
#include <vector>
#include <sstream>
using namespace std;
 
int main() {
 
    int n, m;
    cin >> n >> m;
    // \n 입력을 안 받기 위함.
    cin.ignore();
 
    vector<int> v;
 
    // 문자열로 들어오는 입력값을 변환해 vector에 입력
    string line;
    string nums;
    getline(cin, line);
    stringstream sstream(line); 
    while(getline(sstream, nums, ' ')) {
        v.push_back(stoi(nums));
    }
 
    // 투포인터
    int s, e, total, cnt;
    s = 0;
    e = 0;
    total = v[0];
    cnt = 0;
 
    while(e < n) {
        if(total == m) {
            cnt++;
            e++;
            total += v[e];
        } else if (total < m) {
            e++;
            total += v[e];
        } else {
            total -= v[s];
            s++;
        }
    }
 
    cout << cnt;
 
    return 0;
}

---

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

2003번: 수들의 합 2