[BOJ] 백준 2631 줄세우기

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


이 문제에서는 "순서대로 줄을 맞추어 서있는 아이들" 을 뺀 나머지 아이들을 옮겨주면 되는 문제 입니다.

즉, 나머지 아이들의 수를 출력해주는 문제 입니다.

순서대로 줄을 맞추어 서있는 아이들의 수를 구하기 위해 LIS 알고리즘을 사용해야 합니다.

소스코드 :

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <string>
using namespace std;

int n;

vector<int> box(1001);
//vector<int> cache
vector<int> cache;



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

cin >> n;

cache.push_back(-1);
int ans = 0;
for (int i = 1; i <= n; i++) {
cin >> box[i];
if (cache.back() < box[i]) {
cache.push_back(box[i]);
ans++;
}
else {
auto it = lower_bound(cache.begin(), cache.end(), box[i]);
*it = box[i];
}
}

cout <<n- ans;




}