[백준][C++] 3649: 로봇 프로젝트

문제

풀이

이분 탐색 사용

• 조각을 하나 선택하고 나머지 조각의 길이가 (필요한 길이 - 선택한 조각 길이)라면 문제에 만족된다. 
• 선택한 조각과 맞는 조각을 찾을 때 이분 탐색을 실시한다. 

두 포인터 사용

• 양 옆에서부터 좁혀가며 검사한다. 
• start와 end에서의 조각의 길이의 합이 필요한 길이와 같다면 문제에 만족된다. 

코드

이분 탐색 사용

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> legos;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(nullptr);

    int x, n;
    while (cin >> x >> n)
    {
        x *= 10'000'000;

        for (int i = 0; i < n; ++i)
        {
            int temp;
            cin >> temp;
            legos.push_back(temp);
        }

        sort(legos.begin(), legos.end());

        // 이분 탐색
        // leogs[i]와 들어갈 조각을 이분 탐색한다. 
        // 나머지 조각의 길이는 x - legos[i]이다.
        bool flag = false;
        for (int i = 0; i < n; ++i)
        {
            int find_num = x - legos[i];

            int start = i + 1;
            int end = n - 1;
            while (start <= end)
            {
                int mid = (start + end) / 2;

                // find_num과 맞는 레고를 찾았다면 출력
                if (legos[mid] == find_num)
                {
                    cout << "yes " << legos[i] << " " << legos[mid] << '\n';
                    flag = true;
                    break;
                }

                if (legos[mid] < find_num)
                {
                    start = mid + 1;
                }
                else
                {
                    end = mid - 1;
                }
            }

            if (flag)
            {
                break;
            }
        }

        // 찾지 못 했다면 danger 출력
        if (flag == false)
        {
            cout << "danger" << '\n';
        }

        legos.clear();
    }

    return 0;
}

 

두 포인터 사용

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> legos;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(nullptr);

    int x, n;
    while (cin >> x >> n)
    {
        x *= 10'000'000;

        for (int i = 0; i < n; ++i)
        {
            int temp;
            cin >> temp;
            legos.push_back(temp);
        }

        sort(legos.begin(), legos.end());
        
        // 두 포인터
        // 양 옆에서 부터 점차 좁히며 검사
        int start = 0;
        int end = n - 1;
        while (start < end)
        {
            int sum = legos[start] + legos[end];

            if (sum == x)
            {
                cout << "yes " << legos[start] << " " << legos[end] << '\n';
                break;
            }

            if (sum < x)
            {
                start++;
            }
            else
            {
                end--;
            }
        }

        if (start >= end)
        {
            cout << "danger" << '\n';
        }

        legos.clear();
    }

    return 0;
}