알고리즘 공부
백준 2631 줄세우기 [LIS]
kjwkjw
2020. 5. 21. 21:42
https://www.acmicpc.net/problem/2631
2631번: 줄세우기
KOI 어린이집에는 N명의 아이들이 있다. 오늘은 소풍을 가는 날이다. 선생님은 1번부터 N번까지 번호가 적혀있는 번호표를 아이들의 가슴에 붙여주었다. 선생님은 아이들을 효과적으로 보호하기
www.acmicpc.net
#include <iostream>
#include <vector>
using namespace std;
vector<int> v;
vector<int> temp;
int n;
int main(int argc, char** argv)
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int num;
cin>>n;
for (int i = 0; i < n; ++i)
{
cin>>num;
v.push_back(num);
}
temp.push_back(v[0]);
for (int i = 1; i < n; ++i)
{
int idx = temp.size()-1;
if(temp[idx]<v[i]) temp.push_back(v[i]);
else
{
while(idx>=0&&temp[idx]>v[i])
{
idx--;
}
idx++;
temp[idx] = v[i];
}
}
cout<<v.size()-temp.size()<<"\n";
}