[백준OJ] 2015번 수들의 합 4

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

2015번: 수들의 합 4

---

 

풀이

누적합과 Map을 이용해서 문제를 해결했다.

입력과 동시에 1번째수~i번째수의 합을 psum배열에 저장을 해놓음과 동시에, 1~i번째수의 합이 K라면, answer++를 해준다.

 

그런뒤,

psum[i]= 1~i번째까지의 합이라고 했을때, psum[i]-psum[j-1]=k에서 k의 값은 j~i까지의 합이 된다는 개념을 이용해서 문제를 해결한다. 이때, j의 값을 1~i까지 반복을 한다면 O(N²)이 되므로, 시간초과가 나오기때문에, 다른개념으로 접근을 한다.

 

psum[i]값과 k값을 알고있으니, 이항을 시켜 psum[i]-k= psum[j-1]이 되는 값을 찾으면 된다. 이때 map을 이용해서 지나온 누적합 값을 저장해주면된다.

 

 

반응형

코드

#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
using namespace std;

map<int, long long> sub_sum;
int arr[200001] = { 0 }, psum[200001] = { 0 };
long long n, k,answer=0;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> n >> k;
	for (int i = 1; i <= n; i++) {
		cin >> arr[i];
		psum[i] = psum[i - 1] + arr[i];
		if (psum[i] == k) answer++;
	}
	for (int i = 1; i <= n; i++) {
		answer += sub_sum[psum[i] - k];
		sub_sum[psum[i]]++;
	}
	cout << answer;
	return 0;
}