[Algorithm]Baekjoon 2295번 :: 세 수의 합

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

 

 

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
#include <functional>
#include <sstream>
#include <memory.h>
#include <deque>
#include <set>
#include <unordered_set>
#include <thread>
#include <atomic>
 
using namespace std;
 
int n;
int arr[1000];
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> n;
 
    for (int i = 0; i < n; ++i)
    {
        cin >> arr[i];
    }
 
    sort(arr, arr + n);
 
    vector<int> addedTwoNums;
 
    for (int i = 0; i < n; ++i)
    {
        for (int j = i; j < n; ++j)
        {
            addedTwoNums.push_back(arr[i] + arr[j]);
        }
    }
 
    sort(addedTwoNums.begin(), addedTwoNums.end());
 
    for (int i = n - 1; i >= 0; --i)
    {
        int targetNum = arr[i];
 
        for (int j = 0; j < i; ++j)
        {
            int middleNum = arr[j];
 
            if (binary_search(addedTwoNums.begin(), addedTwoNums.end(), targetNum - middleNum))
            {
                cout << targetNum;
                return 0;
            }
        }
    }
}
 
 

 

 

배열이 주어졌을 때, 숫자 세개를 선택해서 더한 숫자가 배열에 있을 경우의 해당숫자 최대값을 구하는 문제이다.

헷갈리지말아야 할 것은, 중복이 된다는 것.

 

{1, 3, 4} 가 있다면 1을 두번선택해도된다.

이렇게 미리 두개의 숫자를 선택한 값들을 배열에 다 담아놓는다.

이 배열을 addedTwoNums라는 변수라고 했을 때,

 

addedTwoNums의 원소 + 나머지숫자 중 임의의 1개 = 어떤 숫자.

 

여기서 결과값인 어떤숫자가 배열에 있을 경우, 일단 문제의 조건에 부합하는 숫자가 된다. 이 값의 최대값을 구하는게 목표.

 

저 식을 다시 바꾸면

 

어떤 숫자 - 임의의 1개 = addedTwoNums의 원소 가 된다.

 

그러니 반복문을 이중으로 돌면서 어떤숫자 - 임의의 1개인 숫자가 addedTwoNums에 있는지만 찾아주면 된다.

이 때, 임의의 숫자가 있는지를 판단하기위해 이분탐색을 하면 된다.

물론 그러기위해서 addedTwoNums는 정렬이 되어있어야 한다.

 

정렬된 숫자들 중 특정숫자를 찾는 함수정도는 직접 구현할 필요가 사실 없으니, 위의 코드처럼 binary_search를 통해 찾아주면 된다.

타겟값을 뒤에서부터, 즉 큰값부터 찾기 때문에, 첫발견한 타겟값이 곧 문제에서 원하는 답이 된다.

물론 그러기위해서 arr도 정렬을 시켜놔야된다.

 

정렬을 안해도 끝까지 탐색하면서 최대값 업데이트하면 구할수야 있긴 하지만 굳이 그럴필요는 없으니까...