[알고리즘] C++ 백준 2295 세 수의 합

백준 2295

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

2295번: 세 수의 합

풀이 전 나의 생각

N개의 자연수로 이루어진 집합 U에서 3개의 선택된 수의 합이 집합 U에

포함되어 있어야 하며 최대의 수가 되는 값을 구해야한다.

 

조건으로 알 수 있는 것들

- N(5 <= N <= 1000) -> N의 배열범위를 1001로 설정한다.

- U는 20억보다 작다. -> 자연수는 int형으로 설정한다.

- x, y, z, k가 서로 같아도 된다. -> x, y, z, k가 중복될 수있다.

 

Solution

아무리 N이 1000의 범위를 가진다해서 for문으로만 풀려고 하면 안된다.

세 수를 더하려면 벌써 3중for문이 쓰이고 그 안에서 합의 값이 포함되어있는지

확인해야 되기 때문에 for문이 하나 더 쓰인 4중 for문을 써야한다.

1000 * 1000 * 1000 * 1000 의 계산을 진행해야 하는데 아무리 생각해도 횟수가 너무 많다.

 

그렇기 때문에 이분탐색을 적절하게 이용하여 문제를 풀어내야한다.

 

1. 가능한 모든 수의 합을 구한다.

for (int i = 0; i < N; i++)
	{
		for (int j = i; j < N; j++)
		{
			sum.push_back(arr[i] + arr[j]);
		}
	}

x, y, z, k가 서로 같아도 되기 때문에 모든 경우의 합을 구해야한다.

 

2. 이분탐색을 위한 정렬을 진행한다.

sort(arr, arr + N);
sort(begin(sum), end(sum));

arr은 최대의 값을 구하기 위한 정렬이고

sum은 올바른 이분탐색을 위한 정렬이다.

 

3. arr[i] - arr[j]의 값을 이분탐색으로 찾아낸다.

for (int i = N - 1; i >= 0; i--)
	{
		for (int j = i; j >= 0; j--)
		{
			int search_val = arr[i] - arr[j];
			bool exist = binary_search(begin(sum), end(sum), search_val);

			if (exist)
			{
				cout << arr[i];
				return 0;
			}
		}
	}

최대값을 구하기 위하여 for문은 N의 끝값부터 0까지 줄어들며 진행된다.

 

다음으로 arr[i] - arr[j]를 해서 값을 이분탐색을 진행한다.

이유는 예를 들어 2, 3, 5, 10, 18의 집합에서 arr[i]가 18이고 arr[j]가 10이라고 가정하면

18 - 10 = 8이 나올 것이다. 18을 구하기 위해서 10은 이미 포함돼있는 상태기 때문에

나머지 8을 미리 구해놓은 두 수의 합 벡터에서 찾아 더해준다면 10 + 미리구해 놓은 두 수의 합 = 18이 성사되는 것이다.

따라서 이분탐색을 하여 arr[i] - arr[j]의 값이 존재한다면 현재 arr[i]가 최대값이 되는 것이다.

 

 

풀이

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <string>
#include <queue>
#include <string.h>
#include <limits.h>
#include <cstdio>

using namespace std;
int arr[1001];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	vector<int> sum;

	int N;
	cin >> N;

	for (int i = 0; i < N; i++)
	{
		cin >> arr[i];
	}

	for (int i = 0; i < N; i++)
	{
		for (int j = i; j < N; j++)
		{
			sum.push_back(arr[i] + arr[j]);
		}
	}

	sort(arr, arr + N);
	sort(begin(sum), end(sum));

	for (int i = N - 1; i >= 0; i--)
	{
		for (int j = i; j >= 0; j--)
		{
			int search_val = arr[i] - arr[j];
			bool exist = binary_search(begin(sum), end(sum), search_val);

			if (exist)
			{
				cout << arr[i];
				return 0;
			}
		}
	}
}