[G3] 백준 2143번 두 배열의 합 C++ 누적 합, 해시맵, 브루트포스 알고리즘

리뷰

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

AC를 받긴 했느데 사용한 메모리랑 시간이 어마무시했다, 알고리즘 분류에 이분탐색이 있던데 그게 최적해일까?

n값이 적어 가질 수 있는 모든 부배열의 합을 구하는 부분은 1000 * 1000 / 2로 쉽게 구해질 듯 했는데 모르겠다.

 

 

전역 변수

• t : A와 B의 부배열의 합을 만족하는 수를 저장할 변수
• n : A배열의 크기를 저장할 변수
• m : B배열의 크기를 저장할 변수
• A : A배열의 i번째 값을 입력을 받기 위한 변수
• B : B배열의 i번째 값을 입력을 받기 위한 변수
• sumA : A배열의 누적합을 저장하기 위한 배열
• sumB : B배열의 누적합을 저장하기 위한 배열
• dicA : A부배열의 합을 key로, 개수를 value로 저장하기 위한 해시맵
• dicB : B부배열의 합을 key로, 개수를 value로 저장하기 위한 해시맵

 

함수

없음

 

 

문제풀이

1. t, n을 입력 받고, 누적합을 저장할 prefix를 0으로 초기화 해준다.
2. n개의 요소를 입력 받고, 입력 받을 때 마다 prefix에 입력받은 값을 더해준다.
3. sumA에 해당 번째까지의 누적합을 저장해 주고, 현재까지의 누적합을 dicA에 저장해 준다.
4. 이전까지의 누적합을 순회하며 현재까지의 누적합에서 빼준 값을 dicA의 키로 사용하여 값을 증가시킨다.
5. m을 입력 받고, prefix를 다시 0으로 초기화 해준다.
6. m개의 요소를 입력 받고, 2 ~ 4번의 로직을 B배열에 적용시켜 준다.
7. 개수를 저장할 변수 ans를 0으로 초기화 해준다.
8. dicA를 순회하며 t에서 현재 키값을 빼준값을 key로 저장해 준다.
9. dicB에 key를 키로하는 값이 존재할 경우 ans에 dicB의 현재 값과 dicA의 현재 값을 곱해주고 더해준다.
10. dicA순회를 마친 경우 ans에 저장된 값을 출력해 준다.

 

트러블 슈팅

1. ans의 크기가 int범위를 벗어나 68%에서 틀렸다, long long을 고쳐주니 AC를 받게 되었다.
2. AC 이후 최적화 과정에서 unordered_map을 map으로 변경해 보았는데 메모리 초과가 출력되었다.

 

참고 사항

• dicA, dicB의 value의 타입도 long long으로 변경 해주어야 곱하여 ans에 더할 때 오버플로우를 막을 수 있다.

 

정답 코드

#include<iostream>
#include<unordered_map>
#define ll long long
using namespace std;

int t, n, m, A, B, sumA[1000], sumB[1000];
unordered_map<int, ll> dicA, dicB;

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

	cin >> t;

	cin >> n;
	ll prefix = 0;
	for (int i = 0; i < n; ++i) {
		cin >> A;
		prefix += A;
		sumA[i] = prefix;
		dicA[prefix]++;
		for (int j = 0; j < i; ++j) dicA[sumA[i] - sumA[j]]++;
	}

	cin >> m;
	prefix = 0;
	for (int i = 0; i < m; ++i) {
		cin >> B;
		prefix += B;
		sumB[i] = prefix;
		dicB[prefix]++;
		for (int j = 0; j < i; ++j) dicB[sumB[i] - sumB[j]]++;
	}

	ll ans = 0;
	for (const auto& d : dicA) {
		int key = t - d.first;
		if (dicB[key]) ans += dicB[key] * d.second;
	}
	cout << ans;
}