백준 2143번 두 배열의 합

< 백준 2143번 두 배열의 합 - 마포 코딩박 >

사용한 알고리즘: map


 임의의 수 T 와 두 배열 A, B 가 주어졌을 때 A 와 B 의 부배열의 합으로 T 를 만들 수 있는 경우의 수를 구하는 문제였습니다.

 풀이는 다음과 같습니다.
(1) (코드 17~24)
 A 의 모든 부배열로 만들 수 있는 값을 map에 저장합니다.
 예를들어 A[1]~A[3] , A[2]~A[7] 의 두 부배열이 10 이라는 값을 만들면 map[10]=2 입니다.

(2) (코드 25~33)
 T - ( B 의 모든 부배열로 만들 수 있는 값 ) 의 모든 경우를 보며, 이 값을 만들 수 있는 A의 부배열의 개수 ( 과정 (1) 에서 구해놓음 ) 가 답이 됩니다.

	#include <bits/stdc++.h>
	using namespace std;
	const int MAX = 1002;
	const int INF = 1000000000;
	typedef long long ll;
	ll T, N, M, A[MAX], B[MAX] ,ans;
	map<ll, ll> Sum;
	int main(){ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
	cin >> T;
	cin >> N;
	for (ll i = 0; i < N; ++i) cin >> A[i];
	cin >> M;
	for (ll i = 0; i < M; ++i) cin >> B[i];
	// A의 모든 부배열의 합 Sum 에 저장
	for (ll i = 0; i < N; ++i){
	ll temp = 0;
	for (ll j = i; j < N; ++j){
	temp+=A[j];
	if(abs(temp)<=INF) Sum[temp]++;
	}
	}
	// T - B 의 모든 부배열 = Sum 값 이면 ans
	for (ll i = 0; i < M; ++i){
	ll temp = T;
	for (ll j = i; j < M; ++j){
	temp -= B[j];
	if(abs(temp)>INF) break;
	ans += Sum[temp];
	}
	}
	cout << ans << '\n';
	return 0;
	}

view raw BOJ 2143.cpp hosted with ❤ by GitHub