2143 sumOfTwoArray

์•Œ๊ณ ๋ฆฌ์ฆ˜(์ด๋ถ„ํƒ์ƒ‰, ๋ˆ„์ ํ•ฉ)

1. A๋ฐฐ์—ด์€ ๊ทธ๋Œ€๋กœ ๋‘๊ณ , B ๋ฐฐ์—ด์€ ๊ฐ€๋Šฅํ•œ ๋ชจ๋“  ๋ˆ„์ ํ•ฉ์˜ ์ง‘ํ•ฉ์„ ๋งŒ๋“ค๊ณ , ๊ทธ๊ฒƒ์„ ์ •๋ ฌํ•จ
		-> ์ด๋•Œ ๊ทธ๋ƒฅ ๋ฐฐ์—ด์— ์ง‘์–ด๋„ฃ์œผ๋ฉด ์ตœ๋Œ€ 500500๊ฐœ์˜ ์›์†Œ๊ฐ€ ์žˆ์–ด์„œ ๋ฉ”๋ชจ๋ฆฌ์—์„œ ๋ฐ•์‚ด๋‚˜๊ณ , ์ฐพ๋Š”๋ฐ ์‹œ๊ฐ„๋„ ๋ฐ•์‚ด๋‚จ
		-> ๋‚œ set์„ ํƒํ–ˆ์Œ
		-> Pair ๊ตฌ์กฐ์ฒด๋ฅผ ์„ ์–ธํ•ด์„œ, ๋ˆ„์ ํ•ฉ๊ณผ ๊ทธ ๋ˆ„์ ํ•ฉ์ด ๋‚˜์˜จ ํšŸ์ˆ˜๋ฅผ ์ €์žฅํ•จ. ๊ทธ๋ฆฌ๊ณ  ์ •๋ ฌ๊ณผ ๋น„๊ต์—ฐ์‚ฐ์ž๋ฅผ ์˜ค๋ฒ„๋กœ๋”ฉํ•˜์—ฌ set์—์„œ ํ™œ์šฉํ•  ์ˆ˜ ์žˆ๊ฒŒํ•จ
		-> B์˜ ๋ˆ„์ ํ•ฉ์„ ํ•˜๋‚˜์”ฉ ๋งŒ๋“ค์–ด๊ฐ€๋ฉฐ, set์— ์žˆ๋Š”์ง€ ํ™•์ธ -> ์žˆ์œผ๋ฉด set์— ์ด๋ฏธ ์žˆ๋Š” Pair ๊ฐ์ฒด์˜ count์— 1์„ ๋”ํ•˜๊ณ , ์ƒˆ๋กœ์šด pair ๊ฐ์ฒด์— ๋„ฃ์Œ.
									๊ทธ ๋‹ค์Œ, ์›๋ž˜ ์žˆ๋˜ Pair ๊ฐ์ฒด๋ฅผ ์ง€์šฐ๊ณ , ์ƒˆ๋กœ๋งŒ๋“  Pair ๊ฐ์ฒด๋ฅผ ์ง‘์–ด๋„ฃ์Œ
								     -> ์—†์œผ๋ฉด set์— ๊ตฌํ•œ ๋ˆ„์ ํ•ฉ๊ณผ count์— 1์„ ๋„ฃ์–ด ๋งŒ๋“  Pair ๊ฐ์ฒด๋ฅผ set์— ์‚ฝ์ž…
2. A๋ฐฐ์—ด์˜ ๋ˆ„์ ํ•ฉ์„ ํ•˜๋‚˜์”ฉ ๋งŒ๋“ค์–ด๊ฐ€๋ฉฐ B์— (T-๋ˆ„์ ํ•ฉ)์„ ๊ฐ€์ง€๋Š” Pair๊ฐ์ฒด๊ฐ€ ์žˆ๋Š” ์ง€ ํ™•์ธ
	-> ์žˆ์œผ๋ฉด, ๊ทธ ๊ฐ์ฒด์˜ count๋ฅผ ์ „์ฒด count์— ๋”ํ•จ
	-> ์—†์œผ๋ฉด, ๊ทธ๋ƒฅ ํŒจ์Šค
3. ์ „์ฒด count๋Š” int ๋ฒ”์œ„๋ฅผ ๋„˜์„ ์ˆ˜ ์žˆ์Œ

์ฃผ์˜์ 

1. set์— ๊ตฌ์กฐ์ฒด๋ฅผ ๋„ฃ์„๋•Œ, ๊ตฌ์กฐ์ฒด ์•ˆ์— ์˜ค๋ฒ„๋กœ๋”ฉ์„ ์„ ์–ธํ•˜๋Š” ๊ฒฝ์šฐ ๋‹ค์Œ์ฒ˜๋Ÿผ ํ•ด์•ผํ•œ๋‹ค.
	bool operator < (const Pair& p) const{
		return value < p.value;
	}
	์•ˆ๊ทธ๋Ÿผ ์˜ค๋ฅ˜๋‚จ

์ฝ”๋“œ

#include <iostream>
#include <set>
#define MAX_N 1000
 
using namespace std;
 
typedef struct Pair {
	int value;
	int count;
	bool operator < (const Pair& p) const{
		return value < p.value;
	}
	bool operator == (const Pair&  p) const{
		return value == p.value;
	}
} Pair;
 
int A[MAX_N];
int B[MAX_N];
set<Pair> Bset;
int numOfA, numOfB, T;
 
void makeBSet();
long long getCount();
 
int main() {
	cin >> T >> numOfA;
	for (int i = 0; i < numOfA; i++)
		cin >> A[i];
	cin >> numOfB;
	for (int i = 0; i < numOfB; i++)
		cin >> B[i];
 
	makeBSet();
	cout << getCount();
}
 
void makeBSet() {
	for (int i = 0; i < numOfB; i++) {
		int arraySum = 0;
		for (int j = i; j < numOfB; j++) {
			arraySum += B[j];
			Pair temp = { arraySum, 1 };
			set<Pair>::iterator iter = Bset.find(temp);
			if (iter != Bset.end()) {
				temp.count += iter->count;
				Bset.erase(iter);
			}
			Bset.insert(temp);
		}
	}
}
 
long long getCount() {
	long long count = 0;
	for (int i = 0; i < numOfA; i++) {
		int arraySum = 0;
		for (int j = i; j < numOfA; j++) {
			arraySum += A[j];
			set<Pair>::iterator iter = Bset.find({ T - arraySum, 0 });
			if (iter != Bset.end())
				count += iter->count;
		}
	}
	return count;
}