# [Gold IV] 수들의 합 4 #### [문제링크](https://www.acmicpc.net/problem/2015) ## 문제 설명 <p>A[1], A[2], ..., A[N]의 N개의 정수가 저장되어 있는 배열이 있다. 이 배열 A의 부분합이란 1 ≤ i ≤ j ≤ N인 정수 i와 j에 대해 A[i]부터 A[j]까지의 합을 말한다.</p> <p>N과 A[1], A[2], ..., A[N]이 주어졌을 때, 이러한 N×(N+1)/2개의 부분합 중 합이 K인 것이 몇 개나 있는지를 구하는 프로그램을 작성하시오.</p> ## 입력 <p>첫째 줄에 정수 N과 K가 주어진다. (1 ≤ N ≤ 200,000, |K| ≤ 2,000,000,000) N과 K 사이에는 빈칸이 하나 있다. 둘째 줄에는 배열 A를 이루는 N개의 정수가 빈 칸을 사이에 두고 A[1], A[2], ..., A[N]의 순서로 주어진다. 주어지는 정수의 절댓값은 10,000을 넘지 않는다.</p> ## 출력 <p>첫째 줄에 합이 K인 부분합의 개수를 출력한다.</p> ## 풀이 #### 이 문제는 수열이 주어졌을 때 연속된 부분합이 k가 되는 개수를 구하는 문제입니다. #### 1부터 i까지의 합을 preSum이라고 했을 때 1부터 i-1까지의 합 중에서 preSum-k이 되는 범위를 빼면 k가 되는 범위가 나옵니다. 따라서 1부터 i-1까지 preSum-k가 되는 개수만큼 세면 됩니다. ``` c++ #include<bits/stdc++.h> using namespace std; typedef long long ll; int main() { ios::sync_with_stdio(0); cin.tie(0); ll n, k; cin >> n >> k; map<ll, ll> exist; // i번째 이전까지 등장한 부분합의 개수들 ll cnt=0, preSum=0; for(int i=0;i<n;i++) { ll x; cin >> x; preSum += x; // 현재까지의 합 if(preSum==k) cnt++; // 현재까지의 합이 k가 되면 cnt+1 cnt += exist[preSum-k]; // 현재까지의 합에서 (preSum-k)를 빼면 k가 됨 -> exist[preSum-k]의 값만큼 cnt 증가 exist[preSum]++; // map에서 preSum-k의 개수 1 증가 } cout << cnt; } ```