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;
}