2143 sumOfTwoArray
알고리즘(이분탐색, 누적합)
1
2
3
4
5
6
7
8
9
10
11
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
2
3
4
5
1. set에 구조체를 넣을때, 구조체 안에 오버로딩을 선언하는 경우 다음처럼 해야한다.
bool operator < (const Pair& p) const{
return value < p.value;
}
안그럼 오류남
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#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;
}