#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int arr[1002];
vector<int> two;
int main()
{
//1. Get input value
ios::sync_with_stdio(0), cin.tie(0);
int N; cin >> N;
for (int i = 0; i < N; ++i)
{
cin >> arr[i];
}
//2. Find the multiplication of all elements.
for (int i = 0; i < N; ++i)
{
for (int j = 0; j < N; ++j)
{
two.push_back(arr[i] + arr[j]);
}
}
sort(arr, arr + N);
sort(two.begin(), two.end());
for (int i = N - 1; 0 < i; --i)
{
for (int j = 0; j < i; ++j)
{
if (binary_search(two.begin(), two.end(), arr[i] - arr[j]) == true)
{
cout << arr[i];
return 0;
}
}
}
return 0;
}||사고 과정
처음에는 주어진 수열에서 그 수열에 속한 최대 결과값을 찾는게 막연한 느낌을 받았다.
이런 느낌을 받을 때 정의역과 공역이 확실하면 거꾸로 하는게 대부분이여서 이번에도 거꾸로 해보기로 했다.
그래서 주어진 수열을 오름차순으로 정렬하여 마지막 원소부터 세 원소의 합이 가능한지 살펴보았는데
O(n^3)보다 작은 방법을 찾지 못했다..ㅠ
한시간쯤 시도 후 찾지 못해 다른 사람의 풀이를 보고 다시 혼자 풀어 보았다.
방법은 두 원소의 모든 합을 저장하여 이분탐색으로 찾아가며 풀이하는 방법이였다..
어떻게 보면 무식한 방법인데 시간을 계산해보면 O(N^2 * logN)의 복잡도로 괜찮은 방법이였다.
||사용 기법
- Binary search
||풀면서 느낀 것
- 시간 복잡도 계산을 해보자
시간 복잡도를 대강 보지 말고 내 방법에 대한 복잡도 계산을 해보는 걸 지금부터라도 해야겠다.
- 이러한 유형 기억
이분 탐색에서 이렇게 어떤 수끼리 묶고 탐색을 하는 경우가 많다고 한다. 잘 기억해둘것!
||더 나은 풀이
바뀐 부분만 적으면
//2. Find the multiplication of all elements.
for (int i = 0; i < N; ++i)
{
for (int j = i; j < N; ++j)
{
two.push_back(arr[i] + arr[j]);
}
}
sort(arr, arr + N);
sort(two.begin(), two.end());
for (int i = N - 1; 0 < i; --i)
{
for (int j = i - 1; 0 <= j; --j)
{
if (binary_search(two.begin(), two.end(), arr[i] - arr[j]) == true)
{
cout << arr[i];
return 0;
}
}
}첫번째의 이중 반복문에서 중복 되는 경우를 없애 주었다.
두번째의 이중 반복문에서 i와 같은 값의 j를 빼는 경우를 제외했다.
이러한 처리 후 시간이 반 정도 절약 됐다.
