[더블릿 - 1] 두 배열의 합/arraysum

프로그램 명: arraysum

제한시간: 10 초

한 배열 A[1..n] 에 대해여 부 배열은 1 <= i <= j <= n 인 A[i..j] 를 말한다.

부 배열 A[i..j] 의 합은 A[i]+ ... +A[j] 이다. 원소가 양의 정수인 두 배열 A[1..n] 와 B[1..m] 가 주어져 있다. A 의 부 배열의 합에 B 의 부 배열의 합을 더해서 t 가 되는 모든 부 배열 쌍의 개수를 구하는 프로그램을 작성하시오.

예를들어, A=(1,3,1,2) , B=(1,3,2) 이고 t=5 인 경우, 합이 5 가되는 A 와 B 의 부 배열의 쌍의 개수는 아래와 같다.

A[1] + B[1] + B[2]
= A[1] + A[2] + B[1]
= A[2] + B[3]
= A[2] + A[3] + B[1]
= A[3] + B[1] + B[2]
= A[3] + A[4] + B[3]
= A[4] + B[2]
= 5

프로그램의 실행시간은 10 초를 초과할 수 없다. 부분 점수는 없다.

입력 방법

• 첫째 줄에는 t(t <= 10000) 가 주어진다.
• 둘째 줄에는 배열 A 의 크기 n( n <= 1000) 이 주어지고,
• 셋째 줄에는 A 의 원소들이 A[1] 부터 차례대로 주어진다.
• 넷째 줄에는 배열 B 의 크기 m (m <= 1000)이 주어지고,
• 마지막 줄에는 B 의 원소들이 B[1]부터 차례대로 주어진다.

원소의 값은 1000 을 넘지 않는 양의 정수이며 숫자 사이에는 빈칸이 하나 있다.

출력 방법

합이 t 가 되는 A 와 B 의 부 배열 쌍의 개수를 출력한다. 합이 t 가 되는 부배열의 쌍이 없는 경우에는 숫자 0 을 출력한다.

입출력 예

입력

5
4
1 3 1 2
3
1 3 2

출력

7

출처:koi 고등부 기출






  


배열 A와 B의 최대 개수가 1000이다.
따라서, A,B의 부 배열의 최대 개수는 50500개(1000*1001/2)가 될 수 있다.

힌트처럼, A,B의 누적 값을 저장하는 배열을 만든다면(4바이트 배열시..)
하나당 약 200kb가 필요하므로 상당히 비 효율적이다라고 말할 수 있다.

그러므로, 배열 A,B에서 바로 빈도수를 구하는 방법이 효율적이라고 말할 수 있다.

ps) 처음 두 번 제출 했을 때는
누적합이 t를 초과할 수 있다는 것을 간과하여 틀렸으며
세번 째 제출 하였을 때, 경과 시간 부분에서 2등이 나왔다.
1등과 경과 시간은 0.05초로 같았지만 코드 사이즈가 커서 2등이 되었다.
그래서... 소스의 모든 공백을 없애고 제출하였더니 1등이 됬다.
코드 사이즈 부분에서는 제출 당시 15등이였다. 


 


  


#include 
using namespace std;
 
typedef unsigned int _U;

/*
A, B는 원소 저장용 배열
ACount, BCount는 부 배열로 나올 수 있는 수들의 빈도를 저장하는 배열
t는 t 저장용 변수
ASize, BSize는 A,B 배열의 원소의 개수
i는 for문용 변수
sum은 결과 출력용 변수
*/
_U A[1000], B[1000], \
	ACount[10001], BCount[10001], \
	t, ASize, BSize, \
	i, sum;

/*
bg번째부터 ed-1번째까지
for문을 돌면서 A,B의 부분합을 구하며
각각 ACount, BCount에 빈도수를 저장한다.
*/
inline void accum(_U * ar, _U *bg, _U *ed)
{
	_U ptsum = *bg++;
	for (; bg <= ed; ++bg)
	{
		if (ptsum >= t)
			break;
		++(ar[ptsum]);
		ptsum += *bg;
	}
}
/*
ar은 호출에 따라 ACount, BCount가 됨
br은 호출에 따라 A, B가 됨
sz는 호출에 따라 ASize, BSize가 됨
*/
void accum(_U *ar, _U *br,_U sz)
{
	for (i = 0; i < sz; ++i)
		accum(ar, &br[i], &br[sz]);
}
// 문제의 n과 배열 원소를 입력받는 함수
void in(_U *ar, _U &sz)
{
	cin >> sz;
	for (i = 0; i < sz; ++i)
	{
		cin >> ar[i];
		if (ar[i] >= t)
			--i,--(sz);
	}
}
int main()
{
	cin >> t;// t 저장

	in(A, ASize); // A배열의 길이와 원소 저장
	in(B, BSize); // B배열의 길이와 원소 저장

	accum(ACount, A, ASize); // A배열의 부 배열 빈도수를 구함
	accum(BCount, B, BSize); // B배열의 부 배열 빈도수를 구함

	/*
	for문을 돌며
	t가 나올 수 있는 경우를 sum에 더해준다.
	*/
	for (i = 1; i < t; ++i)
		sum += ACount[i] * BCount[t - i];
	cout << sum << endl;
	return 0;
}


 


  


#include 
using namespace std;
typedef unsigned int _U;
_U A[1000],B[1000],ACount[10001],BCount[10001],t,ASize,BSize,i,sum;
inline void accum(_U *ar,_U *bg,_U *ed){_U ptsum=*bg++;for(;bg<=ed;++bg){if(ptsum>=t)break;++(ar[ptsum]);ptsum+=*bg;}}
void accum(_U *ar,_U *br,_U sz){for(i=0;i>sz;for(i=0;i>ar[i];if(ar[i]>=t)--i,--(sz);}}
int main(){cin>>t;in(A,ASize);in(B,BSize);accum(ACount,A,ASize);accum(BCount,B,BSize);for(i=1;i