(2024-10-31) 1 문제 : 백준 - 1818 (책 정리)

 

골드 2 문제인데, 매우 쉬웠다. 이 문제도 알면 쉽고 모르면 어려운 문제인데 LIS(가장 긴 증가하는 부분 수열) 문제이다.

LIS는 구하는 두 가지 방식이 있는데, 이중반복문을 사용해 N^2으로 구하는 방법과 이진탐색을 사용해 NlogN으로 구하는 방법이다.

 

이 문제는 당연히 NlogN의 방식으로 풀어야 시간초과가 안나는데, 이걸 모르는 사람이 스스로 떠올리기는 쉽지 않을 것이다. LIS 알고리즘을 그대로 적용하면 문제를 해결할 수 있다.

 

#include <iostream>
#include <vector>

void Init()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
}

int main()
{
    Init();

    int NumSize = 0;
    std::cin >> NumSize;

    std::vector<int> Nums(NumSize);
    for (int i = 0; i < NumSize; i++)
    {
        std::cin >> Nums[i];
    }

    std::vector<int> LIS;
    LIS.reserve(NumSize);

    for (int i = 0; i < NumSize; i++)
    {
        auto Iter = std::lower_bound(LIS.begin(), LIS.end(), Nums[i]);

        if (Iter != LIS.end())
        {
            *Iter = Nums[i];
        }
        else
        {
            LIS.push_back(Nums[i]);
        }
    }

    std::cout << NumSize - LIS.size();

    return 0;
}