일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
- boj 2667
- 백준 19238
- boj 2636
- boj 2108
- 2167
- 백준 2661
- 백준 2470
- 백준 2108
- boj 19238
- boj 2470
- boj 2206
- 백준 2206
- 10800
- 백준 2167
- boj 1806
- boj 1503
- boj 1697
- 백준 1697
- 백준 2636
- boj 10800
- 백준 10800
- 백준 2635
- 2636
- 백준 2178
- 백준 1806
- boj 2661
- boj 2167
- boj 2178
- boj 2635
- 백준 1503
- Today
- Total
말랑말랑한 개발자 이야기
[백준 9847번] 4SUM 본문
[백준 9847번] 4SUM
문제
In this task, you are provided with four sets of integers. Your task consists of selecting one integer from each set, such that their sum is 0. You can assume that exactly one such selection exists.
입력
The first line of input contains four numbers, a, b, c, and d, separated by a space character, indicating the number of elements in each of the four sets. Each of these numbers is a positive integer 1 ≤ a, b, c, d ≤ 500. The following a + b + c + d lines contain the elements, each not smaller than −60000 and not larger than 60000. The elements of the first set are listed first, followed by the elements of the second set, etc.
출력
The output consists of the four integers, separated by a space character. The numbers must appear in the order in which they are listed in the input file.
풀이
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
int a, b, c, d; cin >> a >> b >> c >> d;
int aa[500], bb[500], cc[500], dd[500];
for(int i=0;i<a;i++) cin >> aa[i];
for(int i=0;i<b;i++) cin >> bb[i];
for(int i=0;i<c;i++) cin >> cc[i];
for(int i=0;i<d;i++) cin >> dd[i];
vector<pair<int, pair<int, int>>> v;
for(int i=0;i<c;i++){
for(int j=0;j<d;j++){
v.push_back(make_pair((cc[i]+dd[j]), make_pair(cc[i], dd[j])));
}
}
sort(v.begin(), v.end());
for(int i=0;i<a;i++){
for(int j=0;j<b;j++){
int s = -(aa[i] + bb[j]);
int lp = 0;
int rp = v.size();
while(lp <= rp){
int mid = (lp + rp) / 2;
if(v[mid].first < s) lp = mid + 1;
else if(v[mid].first > s) rp = mid - 1;
else{
cout << aa[i] << ' ' << bb[j] << ' ' << v[mid].second.first << ' ' << v[mid].second.second;
return 0;
}
}
}
}
return 0;
}
처음으로 풀어본 영어로 된 문제였다. 이 문제를 풀면서 2번의 시행착오를 거쳤다.
0. 일단 필요한 수를 찾기 위해서 이분탐색을 베이스로 깔았다.
1. 처음에는 삼중포문을 돌고 마지막 배열에서 원하는 값을 찾도록 했다.
-> O(N^3 * logN)으로 최대 500임을 고려했을 때, 시간이 좀 걸렸지만 정답입니다를 받았다.
2. 두번째로 이중포문을 돌고 cc, dd 배열을 합한 값에서 원하는 값을 찾도록 했다.
-> O(N^2 * 2logN)으로 빠른 속도로 정답입니다를 받았다.
N의 범위가 작아서 크게 어렵지는 않았던 것 같다.
'알고리즘 > 백준' 카테고리의 다른 글
[백준 5671번] 호텔 방 번호 (0) | 2021.09.14 |
---|---|
[백준 7453번] 합이 0인 네 정수 (0) | 2021.09.14 |
[백준 19951번] 태상이의 훈련소 생활 (0) | 2021.09.14 |
[백준 13023번] ABCDE (0) | 2021.06.22 |
[백준 1976번] 여행가자 (0) | 2021.06.22 |