백준(boj)2631 - 줄세우기

문제 링크 - https://www.acmicpc.net/problem/2631

👀문제이해 및 풀이방법

dp문제 분류에 있길래 도전해 보았는데 정답률은 높고.. 방법은 생각이 안났다. 어떻게 이전의 정보로 다음 정보를 찾을 까 고민하다가 힌트를 봤다
lis문제였다 .. 이걸 알고 5분만에 클리어했다. 아이디어가 정말 중요한데 lis를 찾고 남은 숫자는 어쩔 수 없이 자리를 옮겨야 한다
이런 유형의 문제를 많이 풀어봐야 실전에서 아이디어가 떠오를 것 같다. 알고리즘은 역시 문제를 많이풀어보는게 답인 것 같다

📝코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class lining{
private:
    vector<int> lis;
    int N;
public:
    lining(){
        std::cin >> N;
    }
    void find_sol(){
        int a;
        for(int i=0;i<N;i++){
            std::cin >>a;
            if(lis.empty())
                lis.push_back(a);
            else if(lis.back()<a)
                lis.push_back(a);
            else 
                *lower_bound(lis.begin(),lis.end(),a) = a;
        }
        std::cout << N-lis.size()<<'\n';
    }
};
int main(){
    cin.tie(NULL);cout.tie(NULL);
    ios_base::sync_with_stdio(false);
    lining li;
    li.find_sol();

    return 0;
}