[백준 2143] 두 배열의 합 (C++)

문제 링크: www.acmicpc.net/problem/2143

2143번: 두 배열의 합

1. 주의할 점

- 메모리 제한이 작다. 메모리를 최대한 적게 쓰도록 한다

- Map을 1개 사용하고, 이분탐색을 통해 답을 유추한다

 

2. 구현

- A배열과 B배열을 입력받은 후, A배열에서 만들 수 있는 부분 배열을 Ma Map에 저장한다(숫자, 해당 숫자를 만들 수 있는 개수)

- B배열의 부분 배열을 구할 때마다 Map에 (T - B의 부분배열 합) 값이 있는지 확인한다. 있다면 Map의 2번째 인자(해당 숫자를 만들 수 있는 개수)만큼 더한다

- Cal() 함수에서 위의 과정들을 다 해서 다소 복잡해 보일 수 있다

 

#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
using namespace std;
map<long long, long long> ma;
int arr[2][1000];
long long target, result = 0, diff;
int na, nb, val;

void cal(int num) {
	int len = (num == 0) ? na : nb;
	int sum = arr[num][0];
	map<long long, long long> m;
	vector<long long > v, dup;
	map<long long, long long> ::iterator it;
	for (int i = 0; i < len; i++) {
		val = arr[num][i];
		if (num == 0) {
			if (m.find(val) == m.end()) 
				m[val] = 1;			
			else 
				m[val] += 1;			
		}
		else {
			diff = target - val;
			it = ma.find(diff);
			if (it != ma.end()) 
				result += (it->second);			
		}
		v.push_back(val);
	}
	for (int t = 1; t <= len; t++) {
		for (int i = t; i < len; i++) {
			val = arr[num][i] + v[i - t];
			if (num == 0) {
				if (m.find(val) == m.end())
					m[val] = 1;
				else
					m[val] += 1;
			}
			else {
				diff = target - val;
				it = ma.find(diff);
				if (it != ma.end())
					result += (it->second);
			}
			dup.push_back(val);
		}
		v = dup;
		dup.clear();
	}
	if (num == 0) ma = m;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> target >> na;
	for (int i = 0; i < na; i++)
		cin >> arr[0][i];
	cin >> nb;
	for (int i = 0; i < nb; i++)
		cin >> arr[1][i];
	cal(0);
	cal(1);
	cout << result;
	return 0;
}