[BOJ 2015 // C++] 수들의 합 4

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 2015번 문제인 수들의 합 4이다.
문제는 아래 링크를 확인하자.

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

2015번: 수들의 합 4

구간 [L,R](L>1)의 수의 합은 [1,R] 구간의 수의 합에서 [1,L-1]의 수의 합을 빼는 것으로 계산해낼 수 있다.

 

이를 이용해 첫 항부터 i번째 항까지의 누적합의 값들을 관리하는 것으로 문제를 빠르게 해결할 수 있다.

 

구체적으로, [1,R] 구간의 수의 합 S를 알고 있을 때, [1,r](r<R)의 구간의 합이 S-K인 r의 개수를 구해낼 수 있다면 R로 끝나면서 합이 K인 구간의 개수를 구해낼 수 있다. 이를 R을 1씩 증가시키면서 반복하는 것으로 문제를 해결할 수 있다.

 

아래는 제출한 소스코드이다.

#include <iostream>
#include <map>
using namespace std;
typedef long long ll;

int N, K;
int psum;
map<int, int> mp;
ll ans;

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

	mp.insert(make_pair(0, 1));

	cin >> N >> K;
	for (int i = 0; i < N; i++) {
		int x; cin >> x;
		psum += x;
		
		if (mp.count(psum - K)) ans += mp[psum - K];
		if (mp.count(psum)) mp[psum]++;
		else mp.insert(make_pair(psum, 1));
	}

	cout << ans;
}