[C/C++] 백준 - 2295번 : 세 수의 합

https://www.acmicpc.net/problem/2295

2295번: 세 수의 합

문제

N(5 ≤ N ≤ 1,000)개의 자연수들로 이루어진 집합 U가 있다. 이 중에서 적당히 세 수를 골랐을 때, 그 세 수의 합 d도 U안에 포함되는 경우가 있을 수 있다. 이러한 경우들 중에서, 가장 큰 d를 찾으라.

예를 들어 {2, 3, 5, 10, 18}와 같은 집합이 있다고 하자. 2+3+5 = 10이 되고, 이 수는 집합에 포함된다. 하지만 3+5+10 = 18이 되고, 이 경우가 세 수의 합이 가장 커지는 경우이다.

입력

첫째 줄에 자연수 N이 주어진다. 다음 N개의 줄에 차례로 U의 원소가 하나씩 주어진다. 주어진 U는 집합이 되므로 입력되는 두 수가 같아서는 안 된다. U의 원소는 200,000,000보다 작거나 같은 자연수이다. 답이 항상 존재하는 경우만 입력으로 주어진다.

출력

우리가 x번째 수, y번째 수, z번째 수를 더해서 k번째 수를 만들었다라고 하자. 위의 예제에서 2+3+5=10의 경우는 x, y, z, k가 차례로 1, 2, 3, 4가 되며, 최적해의 경우는 2, 3, 4, 5가 된다. k번째 수가 최대가 되도록 하는 것이 목적이다. x, y, z, k가 서로 같아도 된다. 이때, k번째 수를 출력하면 된다.

 

집합U에서 세 수를 골랐을 때, 그 세 수의 합 d도 U안에 포함되어있는 경우 중 가장 큰 값을 구하는 문제이다.

이분탐색을 적당히 이용해서 해결할 수 있는 문제이다.

 

우선, 2가지 수로 만들 수 있는 값을 모두 만들어본다. 중복이 가능하기에 2중 for문을 이용해서 중복허용하는 모든 값들을 만들어 vector에 모두 넣어준다. 모든 값들을 넣어주었다면 이제 이분탐색을 이용해야하므로 모두 정렬을 해준다.

 

그리고 이제 여기서 이분탐색을 어떻게 사용하냐면, 세 수의 합이 집합U 안에 존재할 때 가장 큰 값을 구해야하므로

for(int i=v.size()-1;i>0;i--){
	for(int j=0;j<i;j++){
    	int Data = v[j] - v[i];
    }
}

위에 Data값이 아까 우리가 만들어놓은 2가지 수의 합 벡터에서 찾아야할 값이 되는 것이다.

위 과정을 이분탐색을 이용한다면 시간 내 해결이 가능하다

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<vector>
#include<deque>
#include<queue>
#define MAX_SIZE 1003

using namespace std;

void solution(vector<int> value, vector<int> Temp) {
	bool isEnd;
	sort(Temp.begin(), Temp.end());
	for (int i = value.size() - 1; i > 0; i--) {
		for (int j = 0; j < i; j++) {
			isEnd = false;
			int Data = value[i] - value[j];
			int left = 0, right = Temp.size();
			while (left <= right) {
				int mid = (left + right) / 2;
				if (Temp[mid] == Data) {
					cout << value[i] << endl;
					isEnd = true;
					break;
				}
				if (Temp[mid] < Data) left = mid + 1;
				else right = mid - 1;
			}
			if (isEnd) break;
		}
		if (isEnd) break;
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N; cin >> N;
	vector<int> v;
	for (int i = 0; i < N; i++) {
		int x; cin >> x;
		v.push_back(x);
	}
	sort(v.begin(), v.end());

	vector<int> Temp;
	for (int i = 0; i < N; i++) {
		for (int j = i; j < N; j++) {
			Temp.push_back(v[i] + v[j]);
		}
	}
	solution(v, Temp);

	return 0;
}