[G4] 백준 2015번 수들의 합 4 C++ 해시맵, 누적합

리뷰

 

구간의 합이 특정 값이 되는 구간의 개수를 구하는 문제

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

 

전역 변수

• dic : 특정 구간의 누적합을 key로 갖고, 그러한 누적합의 개수를 value로 받는 해시맵 long long, int 타입
• total, ans : 누적합 정보를 저장할 변수total, 인접한 수열의 합이 k인 수열의 개수 ans, long long타입으로 초기화 한다.
• n, k, : 수열의 길이 n, 찾을 값 k, 

 

함수

없음

 

 

문제풀이

1. n, k를 입력 받고, sum배열의 1 ~ n번째 인덱스에 누적합 정보를 저장해 준다.
2. 다시 1 ~ n번의 정보를 탐색하며 ans에 현재 누적합 인덱스에서 k를 뺀 값의 개수를 더해준다.
3. 이후 현재 누적합 정보를 키로 갖는 dic의 개수를 증가 시켜준다.
4. 만약 현재 누적합이 k와 같다면 ans를 증가시켜 주어야 한다.

 

참고 사항

누적합 값이 매우 커질 수 있기 때문에 배열 인덱스가 아닌 map을 사용하여 누적합 정보를 관리해 준다.

이전 누적합 정보는 dic을 통해 관리되기 때문에 입력과 동시에 처리해 줘도 된다.

 

 

정답 코드

#include<iostream>
#include<unordered_map>
#define ll long long

using namespace std;

unordered_map<ll, int> dic;
ll total = 0, ans = 0;
int n, k;

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

	cin >> n >> k;
	for (int i = 1; i <= n; i++) {
		ll a; cin >> a;
		total += a;
		if (total == k) ans++;
		ans += dic[total - k];
		dic[total]++;
	}
	cout << ans;
}