[BOJ/백준][Gold4] 7570 : 줄 세우기 (C++)

https://www.acmicpc.net/problem/7570

7570번: 줄 세우기

 

 

[난이도] Gold4
[유형] DP

[풀이]
값이 1씩 증가하는 LIS를 구한다. 이 LIS에 포함되지 않은 숫자들은
모두 앞 또는 뒤로 옮겨줘야 정렬을 할 수 있기 때문에 N-(LIS의 길이) 가 정답이다.

 

#include <algorithm>
#include <cstdio>
using namespace std;
int N,dp[1000001],v,ans;
int main(){
    scanf("%d",&N);
    for(int i=1;i<=N;i++){
        scanf("%d",&v);
        dp[v] = dp[v-1]+1;
        ans = max(ans,dp[v]);
    }
    printf("%d",N-ans);
}

 

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/7570.cpp