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

2015번 : 수들의 합 4

---

문제)

A[1], A[2], ..., A[N]의 N개의 정수가 저장되어 있는 배열이 있다. 이 배열 A의 부분합이란 1 ≤ i ≤ j ≤ N인 정수 i와 j에 대해 A[i]부터 A[j]까지의 합을 말한다.

N과 A[1], A[2], ..., A[N]이 주어졌을 때, 이러한 N×(N+1)/2개의 부분합 중 합이 K인 것이 몇 개나 있는지를 구하는 프로그램을 작성하시오.

 

 

 

입력 :

첫째 줄에 정수 N과 K가 주어진다. (1 ≤ N ≤ 200,000, |K| ≤ 2,000,000,000) N과 K 사이에는 빈칸이 하나 있다. 둘째 줄에는 배열 A를 이루는 N개의 정수가 빈 칸을 사이에 두고 A[1], A[2], ..., A[N]의 순서로 주어진다. 주어지는 정수의 절댓값은 10,000을 넘지 않는다.

 

 

 

출력 :

첫째 줄에 합이 K인 부분합의 개수를 출력한다.

 

 

 

 

 

풀이)

자세한 풀이는 다음 링크를 참고해주세요~

[알고리즘] 누적합 (Prefix Sum)

 

 

// 2015. 수들의 합 4
#include <iostream>
#include <vector>
#include <map>
 
using namespace std;
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    int n;
    long long k;
    cin >> n >> k;
 
    vector<long long> vec(n + 1, 0);
    vector<long long> prefix(n + 1, 0);
 
    for (int i = 1; i < n + 1; i++)
    {
        cin >> vec[i];
        prefix[i] = prefix[i - 1] + vec[i];
    }
 
    map<long long, int> cnt;
    long long answer = 0;
    for (int i = 0; i < n + 1; i++)
    {
        answer += cnt[prefix[i] - k];
        cnt[prefix[i]]++;
    }
    cout << answer;
 
    return 0;
}

---

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

2015번: 수들의 합 4