BOJ 2631 - 줄 세우기

그리디(?)적으로 생각했을 때 그냥 자기 자리로 찾아가는 녀석의 수를 줄이면 된다.

문제가 원하는 것은 오름차순으로 정렬을 하는데 움직이는 학생의 수를 줄이는 것이므로 전체에서 오름차순으로 정렬되어 있는 최대 학생의 수를 빼면 된다는 것을 쉽게 알 수 있다.

 

즉 전체에서 lis를 빼주면 된다.

int main() {
    fastio;
    int n;
    cin>>n;
    vector<int>arr(n);
    for(auto&v:arr)cin>>v;
    vector<int>dp(n,0);
    int ans=0;
    for(int i=0; i<n; i++){
        dp[i]=1;
        for(int j=0; j<i; j++){
            if(arr[i]>arr[j])dp[i]=max(dp[i],dp[j]+1);
        }
        ans=max(ans,dp[i]);
    }
    cout<<n-ans;
    return 0;
}