땡글이LAB
[백준] 2295 세 수의 합 - C++ 본문
이 2295번 문제에 가장 간단하게 접근하는 방법은 arr[i] + arr[j] + arr[k] = arr[m] 방식으로 시간복잡도가 O(N^4)인 방법이 있을테고, arr[m]을 찾는 방식을 이분탐색으로 바꿔주면, O(N^3 * logN) 이 될 것이다. 이 문제가 정답율이 낮은 이유도 이렇게 다들 생각을 많이 하고 제출했더니 메모리 초과가 나거나 시간초과가 난 것 같다.
O(N^3 * logN) 코드는 다음과 같다. 이렇게 풀면 틀립니다
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int N;
int arr[1005];
vector<int> three;
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> N;
for (int i = 0; i < N; i++) {
cin >> arr[i];
}
sort(arr, arr + N);
for (int i = 0; i < N; i++) {
for (int j = i; j < N; j++) {
for (int k = j; k < N; k++) {
three.push_back(arr[i] + arr[j] + arr[k]);
}
}
}
sort(three.begin(), three.end());
int ans = 0;
for (int i = 0; i < N; i++) {
if (binary_search(three.begin(), three.end(), arr[i])) {
ans = max(ans, arr[i]);
}
}
cout << ans;
}
하지만, 이보다 더 좋은 방법이 있다. 식을 조금 변형해서 arr[i] + arr[j] = arr[m] - arr[k] 로 해서 arr[i] + arr[j]를 two라는 벡터 변수에 저장해둔 뒤, arr[m] - arr[k]가 two 벡터에 있는지 이분탐색으로 탐색하면 시간 복잡도는 O(N^2 * logN)이 될 것이다. 이 방법을 알아내기만 하면 문제는 간단해진다.
정답코드는 다음과 같다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int N;
int arr[1005];
vector<int> two;
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> N;
for (int i = 0; i < N; i++) {
cin >> arr[i];
}
sort(arr, arr + N);
for (int i = 0; i < N; i++) {
for (int j = i; j < N; j++) {
two.push_back(arr[i] + arr[j]);
}
}
sort(two.begin(), two.end());
int ans = 0;
for (int i = 0; i < N; i++) {
for (int j = i; j < N; j++) {
if (binary_search(two.begin(), two.end(), arr[j] - arr[i])) {
ans = max(ans, arr[j]);
}
}
}
cout << ans;
}
'Algorithm > Problem Solve' 카테고리의 다른 글
[백준] 13144 List of Unique Numbers - C++ (0) | 2022.02.09 |
---|---|
[백준] 10942 팰린드롬? - C++ (0) | 2022.02.08 |
[백준] 2805 나무 자르기 - C++ (0) | 2022.02.07 |
[프로그래머스] 메뉴 리뉴얼 - 2021 KAKAO BLIND RECRUITMENT (0) | 2022.01.18 |
Comments