[백준 9847번] 4SUM

[백준 9847번] 4SUM

www.acmicpc.net/problem/9847

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의 범위가 작아서 크게 어렵지는 않았던 것 같다.