[백준][C++] 2352: 반도체 설계

문제

풀이

이분 탐색을 사용한다. 가장 긴 증가하는 부분 수열을 찾는 문제이다. 내가 알던 방법은 O(N * N)으로 전체 계산 수가 16억이 되어 시간 초과가 발생한다. 

• 입력이 들어오면서 검사를 실시한다. 
• 입력값이 현재 수열의 가장 끝에 있는 수를 초과한 경우 바로 수열에 추가된다. 
• 이하일 경우엔 이분 탐색을 실시한다.
  • 현재 수열에서 입력값 이하의 값 중, 최댓값을 입력값으로 교체한다. 
• 이렇게 하면 시간 복잡도가 O(N * logN)으로 줄어든다.

코드

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

using namespace std;

vector<int> nums;

// 기존에 입력된 nums에서 num 이하의 값중에서
// 최댓값을 num으로 교체한다.
void binary_input(int num)
{
    int start = 0;
    int end = nums.size() - 1;

    while (start <= end)
    {
        int mid = (start + end) / 2;
        int current = nums[mid];

        if (current < num)
        {
            start = mid + 1;
        }
        else
        {
            end = mid - 1;
        }
    }

    // 이분 탐색 후 start가 적절한 위치로 설정된다.
    nums[start] = num;
}

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

    int n;
    cin >> n;

    // 첫번째 값은 바로 삽입
    int temp;
    cin >> temp;
    nums.push_back(temp);

    // 입력을 받으면서 검사
    int index = 0;
    for (int i = 1; i < n; ++i)
    {
        int temp_;
        cin >> temp_;

        // 입력 받은 값이 현재 nums의 마지막 수보다 크다면 바로 삽입
        if (nums[index] < temp_)
        {
            nums.push_back(temp_);
            index++;
        }
        // 이하라면 입력받은 값보다 바로 아래로 작은 값을 이분 탐색하여 교체
        else
        {
            binary_input(temp_);
        }
    }

    // nums에 가장 긴 증가하는 부분 수열이 들어간다.
    cout << nums.size();

    return 0;
}