투포인터 - 백준:2143번 두 배열의 합

음 이렇게 생각했다. 일단 A에 대해서 투포인터로 부분합을 좀 구하다가 , B에 대해서도 투포인터로 연산하면 된다고 생각했는데 틀린 부분이 A에 대해 경우가 다 나오지 않는다.

 

#define _CRT_SECURE_NO_WARNINGS
#define debug 0
#include <iostream>
#include <algorithm>
#include <vector>
#include<string.h>

using namespace std;

#define NUM 100001
#define MAXV 987654321
long long int N, M,S;
int arr[NUM],brr[NUM];
long long int T, A, B;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	freopen("input.txt", "r", stdin);

	cin >>T;
	long long int ans = 0;
	long long int sum = 0;

	cin >> A;
	for (int i = 0; i < A; i++) {
		cin >> arr[i];
	}
	cin >> B;
	for (int i = 0; i < B; i++) {
		cin >> brr[i];
	}
	int al = 0, ar = 0;
	int bl = 0, br = 0;
	while (al < A) {
		if (sum > T || ar == A) {
			sum -= arr[al++];
		}
		else {
			sum += arr[ar++];
		}

		bl = 0, br = 0;
		long long int bsum = 0;
		while (bl < B) {
			if (bsum + sum > T || br == B) {
				bsum -= brr[bl++];
			}
			else {
				bsum += brr[br++];
			}

			if (sum > 0 &&bsum > 0 && sum + bsum == T) {
				cout  << al << " " << ar << " " << bl << " "<<br << "\n";
				ans++;
			}
		}//while
	}


	if(ans != MAXV)
		cout << ans << "\n";
	else {
		cout << 0 << "\n";
	}

	return 0;
}

이렇게 나옴

0 1 0 2
0 2 0 1
2 4 2 3
3 4 1 2
4

일단 내가보기엔 A에 대해서는 완전 탐색을 해야한다.

 

음 그렇게 고쳤는데 9%에서 틀렸다. 음 문제를 다시보니 절대값이 1000000을 넘지 않는 정수니까 음수도 포함인거 같다........... 어떻게 하지;; 모르겠따... 음수가 있으면 기존 방법이 안통한다;;

#define _CRT_SECURE_NO_WARNINGS
#define debug 0
#include <iostream>
#include <algorithm>
#include <vector>
#include<string.h>

using namespace std;

#define NUM 100001
#define MAXV 987654321
long long int N, M,S;
int arr[NUM],brr[NUM];
long long int T, A, B;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	freopen("input.txt", "r", stdin);

	cin >>T;
	long long int ans = 0;
	long long int sum = 0;

	cin >> A;
	for (int i = 0; i < A; i++) {
		cin >> arr[i];
	}
	cin >> B;
	for (int i = 0; i < B; i++) {
		cin >> brr[i];
	}
	int al = 0, ar = 0;
	int bl = 0, br = 0;
	for (int al = 0; al < A; al++) {
		sum = 0;
		for (int ar = al; ar < A;ar++) {
			sum += arr[ar];

			if (sum > T)break;

			bl = 0, br = 0;
			long long int bsum = 0;
			while (bl < B) {
				if (bsum + sum > T || br == B) {
					bsum -= brr[bl++];
				}
				else {
					bsum += brr[br++];
				}

				if (sum > 0 && bsum > 0 && sum + bsum == T) {
//					cout << al << " " << ar << " " << bl << " " << br << "\n";
					ans++;
				}
			}//while
			
		}
	}

	if(ans != MAXV)
		cout << ans << "\n";
	else {
		cout << 0 << "\n";
	}

	return 0;
}

 

다시 했는데 틀렸다.

각 배열에서 완전 탐색으로 가능한 모든 T보다 작은 합의 각각의 갯수를 구하고 그것의 경우의 수를 계산했는데 곱셈으로

문제가 T가 1000000000이라 메모리 초과이다.....

 

다시 생각해보자.

#define _CRT_SECURE_NO_WARNINGS
#define debug 0
#include <iostream>
#include <algorithm>
#include <vector>
#include<string.h>

using namespace std;

#define NUM 100001
#define MAXV 987654321
long long int N, M, S;
int arr[NUM], brr[NUM];
long long int a_cnt[NUM] = { 0 }, b_cnt[NUM] = { 0 };
long long int T, A, B;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

		freopen("input.txt", "r", stdin);

	cin >> T;
	long long int ans = 0;
	long long int sum = 0;

	cin >> A;
	for (int i = 0; i < A; i++) {
		cin >> arr[i];
	}
	cin >> B;
	for (int i = 0; i < B; i++) {
		cin >> brr[i];
	}
	int al = 0, ar = 0;
	int bl = 0, br = 0;
	int a_sum = 0,b_sum=0;
	/*
	while(al<A) {
		if (a_sum >= T || ar == A) {
			a_sum -= arr[al++];
		}
		else {
			a_sum += arr[ar++];
		}
		a_cnt[a_sum] += 1;
	}

	while(bl<B) {
		if (b_sum >= T || br == B)  {
			b_sum -= brr[bl++];
		}
		else {
			b_sum += brr[br++];
			
		}
		b_cnt[b_sum] += 1;
	}
	*/
	for (int al = 0; al < A; al++) {
		for (int ar = al; ar < A; ar++) {
			if (a_sum+arr[ar] > T)
				break;
			a_sum += arr[ar];
			a_cnt[a_sum] += 1;

		}
		a_sum = 0;
	}
	for (int bl = 0; bl < B; bl++) {
		for (int br = bl; br < B; br++) {
			if (b_sum +brr[br]> T)
				break;
			b_sum += brr[br];
			b_cnt[b_sum] += 1;

		}
		b_sum = 0;
	}

	for (int i = 1; i < T; i++) {
		ans += (a_cnt[i] * b_cnt[T - i]);
	}


	if (ans != MAXV)
		cout << ans << "\n";
	else {
		cout << 0 << "\n";
	}

	return 0;
}

 

음 답을 봤다 <https://debuglog.tistory.com/155>

내가 놓친 부분은 부분 합을 미리 구할 수 없다 생각한것이다. 부분 합에 따라서 갯수를 세려하니까 불가능한거고 그게 아니라 그냥 값을 구하고 배열로 정렬 시켜놓고 이분탐색으로 구하는 방법이 있네 .....!!

 

접근

• A로 만들 수 있는 부배열의 합을 미리 다 구한다.

• B로 만들 수 있는 부배열의 합을 미리 다 구한다.

• B를 정렬 (바이너리 서치를 위함)

• A의 원소를 하나씩 탐색하며 T와의 차이 값이 B에 몇 개 존재하는 지를 찾는다.

이분탐색을 사용할 생각을 못했다. 경우를 그냥 배열에 나열할 생각을 못했다.

 

얻은게 많은 문제 였다.

 

#define _CRT_SECURE_NO_WARNINGS
#define debug 0
#include <iostream>
#include <algorithm>
#include <vector>
#include<string.h>

using namespace std;

#define NUM 100001
#define MAXV 987654321
long long int N, M, S;
int arr[NUM], brr[NUM];
vector<long long int>as, bs;

long long int T, A, B;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	freopen("input.txt", "r", stdin);

	cin >> T;
	long long int ans = 0;
	long long int sum = 0;

	cin >> A;
	for (int i = 0; i < A; i++) {
		cin >> arr[i];
	}
	cin >> B;
	for (int i = 0; i < B; i++) {
		cin >> brr[i];
	}
	int al = 0, ar = 0;
	int bl = 0, br = 0;
	int a_sum = 0, b_sum = 0;

	for (int al = 0; al < A; al++) {
		for (int ar = al; ar < A; ar++) {
			a_sum += arr[ar];
			as.push_back(a_sum);
		}
		a_sum = 0;
	}
	for (int bl = 0; bl < B; bl++) {
		for (int br = bl; br < B; br++) {
			b_sum += brr[br];
			bs.push_back(b_sum);
		}
		b_sum = 0;
	}
	
	//벡터로 넣고 정렬후 이분탐색으로 원하는 값을 log로 찾을 수 있다.
	sort(bs.begin(), bs.end());

	for (int i = 0; i < as.size(); i++) {
		int a = as[i],b;
		//같은게 있으므로 이렇게 세야한다. ****
		auto lb = lower_bound(bs.begin(), bs.end(), T - a);
		auto ub = upper_bound(bs.begin(), bs.end(), T - a);
		
		ans += (ub - lb);
	}


	if (ans != MAXV)
		cout << ans << "\n";
	else {
		cout << 0 << "\n";
	}

	return 0;
}