[백준 알고리즘] 2143번 두 배열의 합 문제풀이 c++

map에 n배열과 m배열의 가능한 부 배열의 합을 key로 하여 합의 개수를 저장한다.

그 후 map을 전체탐색하여 nmap에서 key가 x일때,

mmap에서 key가 t-x인 경우를 곱한 값을 모두 더하면

두 배열의 부 배열의 합이 t인 모든 경우의 수 개수를 알 수 있다.

 

 

예시

5
4
1 3 1 2
3
1 3 2

 

위 경우에서 각각 map을 채우면

nmap[1] = 2, nmap[2] =1, nmap[3] = 2, nmap[4] =2, nmap[5] = 1, nmap[6] = 1, nmap[7] =1

mmap[1] = 1, mmap[2] = 2, mmap[3] = 1, mmap[4] =1, mmap[5] =1, mmap[6]

와 같이 채워지고,

map탐색을 통해서

nmap[1] * mmap[4] + nmap[2] * mmap[3] + nmap[3] * mmap[2] + nmap[4]*mmap[1] =

2*1 + 1*1 + 2*1 + 2*1 = 7

로 7의 결과를 얻게 된다.

 

#include <iostream>
#include <map>

using namespace std;

int nlist[1000], mlist[1000];
int main(){
	int t;
	int n,m;
	cin >> t;
	cin >> n;
	for(int i=0; i<n; i++){
		cin >> nlist[i];
	}
	cin >> m;
	for(int i=0; i<m; i++){
		cin >> mlist[i];
	}

	map<long long, long long> nmap, mmap;

	long long sum;
	for(int i=0; i<n; i++){
		sum = 0;
		for(int j=i; j<n; j++){
			sum += nlist[j];
			nmap[sum] ++;
		}
	}

	for(int i=0; i<m; i++){
		sum = 0;
		for(int j=i; j<m; j++){
			sum += mlist[j];
			mmap[sum] ++;
		}
	}

	long long  res = 0;
	for(auto x = nmap.begin(); x != nmap.end(); x++){
		if(mmap.find(t - x->first) != mmap.end()){
			res += x->second * mmap[t - x->first];
		}
	}

	cout << res;
	return 0;
}