2015 수들의 합

Link

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

Detail

누적합까지의 아이디어는 (여러개의 부분합을 구해야 함 + 배열의 순서가 변경되지 않음) 을 통해서 빠르게 생각해낼 수 있었다.

다만 배열의 최대 갯수가 20만이기 때문에 ( $N\cdot log(N)$ 이 등장하는 단골 수) 누적합을 구성해두었다고 부분합이 K인 것들의 갯수가 몇개인지 $N^2$ 으로 구할 수 는 없다.

이 과정에서 고민을 하다가. 2시간이 오버되어 검색으로 해답을 알 수 있었다.

1. $[0,i]$ 까지의 합을 set에 저장한다.
2. $[i,j]$의 부분합이 k인 i, j를 구할려면
   1. 각 i마다 $O(N)$ 올바른 j를 set에서 찾는다 $logN$

로 $N\cdot log(N)$ 시간 복잡도를 달성할 수 있다.

Code

#include<bits/stdc++.h>
 
using namespace std;
typedef long long ll;
 
int main() {
	int n, k;
	cin >> n >> k;
 
	vector<int> preSum(n);
	map<int, ll> sumFreq;
	sumFreq[0] = 1;
 
	int num;
	for (int i = 0; i < n; i++) {
		cin >> num;
		if (i == 0) {
			preSum[i] = num;
		} else {
			preSum[i] = preSum[i - 1] + num;
		}
	}
 
 
 
	ll ans = 0;
	for (int i = 0; i < n; i++) {
		if (sumFreq.find(preSum[i] - k) != sumFreq.end()) {
			ans += sumFreq[preSum[i] - k];
		}
 
		sumFreq[preSum[i]]++;
	}
 
	cout << ans << endl;
}