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

풀이 방법 : 누적 합 + 해시

i - j번째까지의 부분 합이 K인 경우의 수를 구하는 문제다.
1 ~ N까지 숫자들의 누적 합을 구해주는 과정에서 i번째 누적합을 구했다 치면
만약 Sum[i] - Sum[j] == K 를 만족하는 Sum[j] 누적합이 이전에 나온 적이 있다면 부분 합이 K인 경우가 있는 것이다.
따라서 누적 합이 나온 횟수를 카운팅을 해줘야하는데 숫자가 커지거나 음수가 나올 수 있으므로 단순 배열이 아닌 해시 테이블 등의 다른 방법을 통해 카운팅 해주는 것이 편할 것이다.
이렇게 누적합의 값이 나온 횟수를 카운팅 해주고 위 조건을 만족하는 경우의 수를 정답에 더해주면 된다.

#include <iostream>
#include <unordered_map>

using namespace std;

int Sum[200001] = {};

int main()
{
	cin.tie(nullptr);
	cout.tie(nullptr);
	ios::sync_with_stdio(false);

	int N, K;
	cin >> N >> K;

	unordered_map<int, long> mapSum;
	
	long Answer = 0;
	for (int i = 1; i <= N; ++i)
	{
		cin >> Sum[i];
		Sum[i] += Sum[i - 1];

		Answer += mapSum[Sum[i] - K];
		++mapSum[Sum[i]];
	}

	Answer += mapSum[K];

	cout << Answer;
}