백준
백준 2015번(Gold 4)
이야기prog
2023. 10. 5. 22:05
이번에는 백준 2015번 수들의 합에 대한 백준문제를 풀어보겠습니다.
https://www.acmicpc.net/problem/2015
2015번: 수들의 합 4
첫째 줄에 정수 N과 K가 주어진다. (1 ≤ N ≤ 200,000, |K| ≤ 2,000,000,000) N과 K 사이에는 빈칸이 하나 있다. 둘째 줄에는 배열 A를 이루는 N개의 정수가 빈 칸을 사이에 두고 A[1], A[2], ..., A[N]의 순서로
www.acmicpc.net
#include <vector>
#include <iostream>
#include <map>
int main() {
std::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0);
long long N, K, sum = 0;
std::cin >> N >> K;
std::map<long long, long long> m;
std::vector<long long> tmp(N + 1, 0);
std::vector<long long> arr(N + 1, 0);
for (int i = 1; i <= N; ++i)
std::cin >> tmp[i];
for (int i = 1; i <= N; ++i) {
arr[i] = arr[i - 1] + tmp[i]; // 부분합 array
}
long long count = 0;
for (int i = 1; i <= N; ++i) {
if (arr[i] == K) count++;
if (m.find(arr[i] - K) != m.end()) count += m[arr[i] - K];
if (m.find(arr[i]) != m.end()) m[arr[i]]++;
else m.insert({arr[i], 1});
}
std::cout << count;
return 0;
}