[C++] 백준 - 두 배열의 합

1. 문제

 

2. 입 출력

 

3. 문제 해설

처음엔 투포인터로 풀려고 노력했다. 양수만 있었다면 투포인터로 충분히 풀 수 있었을텐데 음수가 섞이는 바람에 포인터의 이동 로직이 복잡해져서 다른 방법을 생각해보았다. 

 

N의 제한은 1000 생각보다 크지 않았다. 더 많은 작업을 brute Force하게 수행해도 될 거 같다는 생각이 들었다. 

따라서 모든 부분합의 경우의 수를 구해보기로 했다. 

 

map<long long , long long> amap;
for(int i=1; i <= n; i++) {
	int sumA = 0;
	for(int j=i; j <=n ; j++) {
    	sumA += ns;
        amap[sumA]++;
    }
}

다음과 같은 코드는 O(N^2)보다는 작은 시간 복잡도를 갖는다. i가 커짐에 따라 j반복문의 반복 횟수가 줄어들기 때문이다. 

 

또한 map을 사용한 이유는 map은  O(logN)의 시간복잡도 안에 정렬을 수행해주기 때문이다. 

먼저 들어온 n에 해당하는 수열에 대해 다음과 같이 모든 부분합의 경우의 수 개수를 만들어주었고

 

m에 해당하는 수열들 또한 위의 과정을 수행하면서 T에 해당하는 값에서 m의 부분합 경우의 수를 빼주었을 때 map에 개수가 존재한다면 최종 결과에 더해주며 업데이트한다.

 

한가지 신경써야하는 것은 map의 키와 value가 int를 초과할 수도 있다는 것이다. 만약 한 가지 경우의 수만 계속 나올 경우

1000 * 1000 * 1000 * 1000으로 int의 범위를 넘는다. 따라서 long long 으로 선언해주었다. 

 

#pragma warning (disable:4996)
/*
	풀이
	각각 누적합의 경우의 수를 모두 구해준다. 
	map을 이용해서 자동 정렬이 되도록 해준다.
*/
#include <cstdio>
#include <map>
#define MAX 1002
#define ll long long
using namespace std;
int T;
int n,m;
int ns[MAX];
int ms[MAX];
ll ans;
map <ll, ll> amap;
void input() {
	scanf("%d %d", &T , &n);
	for (int i = 1; i <= n; i++) {
		scanf("%d", &ns[i]);
	}
	scanf("%d", &m);
	for (int i = 1; i <= m; i++) {
		scanf("%d", &ms[i]);
	} // 입력받는다. 
}
void sol() {
	
	for (int i = 1; i <= n; i++) {
		int sumA = 0;
		for (int j = i; j <= n; j++) {
			sumA += ns[j];
			amap[sumA]++;
		}
	} // n들을 입력했을 때 가능한 누적합의 개수 map작성

	for (int i = 1; i <= m; i++) {
		int sumB = 0;
		for (int j = i; j <= m; j++) {
			sumB += ms[j];
			ans += amap[T - sumB];
		}
	}
	printf("%lld\n", ans);
}

int main() {
	input();
	sol();

	return 0;
}