[C++] 백준 2631 줄세우기

 
#include <iostream>
#include <string>
#include <vector>
 
int main()
{
    int N = 0;
    int iMax = 0;
    std::cin >> N;
 
    std::vector<int> DP(N, 0);
    std::vector<int> vec(N, 0);
 
    for (int i = 0; i < N; ++i)
    {
        std::cin >> vec[i];
    }
 
    for (int i = 0; i < N; ++i)
    {
        DP[i] = 1;
 
        for (int j = 0; j < i; ++j)
        {
            if (vec[j] < vec[i] && DP[i] < DP[j] + 1)
                DP[i] = DP[j] + 1;
        }
 
        if (iMax < DP[i])
            iMax = DP[i];
    }
 
    std::cout << N - iMax;
 
    return 0;
}
 

최장증가수열 알고리즘(LIS)를 이용하면 좋다고 합니다

DP[i] < DP[j] + 1을 하는 이유는 이전에 만든 DP에 추가를 한다는 생각으로 풉니다.

최장 증가 부분 수열은 원소가 n개인 배열의 일부 원소를 골라내서 만든 부분 수열 중, 각 원소가 이전 원소보다 크다는 조건을 만족하고, 그 길이가 최대인 부분 수열입니다.

즉 제공된 예제를 LIS로 만들다면

3 7 5 2 6 1 4

3 5 6 이 LIS이다

현재는 최대가 200개 이하 이기 때문에 N제곱으로만 만들었지만 수가 많아진다면 이분탐색으로 해야 할것입니다.