[문제 링크](https://www.acmicpc.net/problem/2295)
💡 이분 탐색/자료 구조/해시를 사용한 집합과 맵/중간에서 만나기
Memory: 8184KB Time: 60ms Code Length: 591B
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
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int N;
int dict[1000];
vector<int> two_sum;
void init() {
cin >> N;
for (int i = 0; i < N; i++) {
cin >> dict[i];
}
sort(dict, dict + N);
}
int main() {
init();
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
two_sum.push_back(dict[i] + dict[j]);
}
}
sort(two_sum.begin(), two_sum.end());
for (int i = N-1; i >=0; i--) {
for (int j = 0; j <= i; j++) {
if (binary_search(two_sum.begin(), two_sum.end(), dict[i]-dict[j])) {
cout << dict[i] << " ";
return 0;
}
}
}
}
이 코드는 주어진 정수 배열에서 두 수를 선택하여 더한 값들을 모두 구한 뒤, 그 합으로 이루어진 새로운 배열을 만든다. 그 후, 새로운 배열을 정렬한 뒤, 원래 배열의 각 요소들을 빼서 나온 값이 새로운 배열에 있는지 이진 탐색을 통해 확인한다. 만약 존재한다면 해당 두 수를 출력하고 프로그램을 종료한다.
