C++) 백준 2015 수들의 합 4

2015번: 수들의 합 4

---

코드

 

#include <algorithm>
#include <iostream>
#include <map>

using namespace std;

map<long long, long long> ma;
long long va[200005];

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

	long long k, cnt = 0;
	int n;

	cin >> n >> k;

	for (int i = 1; i <= n; i++) {
		cin >> va[i];
		va[i] += va[i - 1];
		if (va[i] == k) cnt++;
	}
	for (int i = 1; i <= n; i++) {
		cnt += ma[va[i] - k];
		ma[va[i]]++;
	}
	cout << cnt;
}

 

 

풀이

 

접근 : 수 입력마다 합하여 모든 경우의 합을 찾음

 - 부분합을 구하는 처리를 해보았지만, 실패

 - unordered_set 사용 : 시간 초과

 

누적합을 사용하는 풀이법을 참고하여 해결

1. 누적합 D[ i ~ j ] = D[ 0 ~ i ] - D[ 0 ~ j ]

2. D[ i ~ j ] = K 이므로 D[ i ] - K = D[ j ] 의 식이 성립하므로 D[ j ] 카운팅

3. 입력값이 K인 경우 카운팅