[백준] 2631번 줄세우기

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

문제

입출력

문제 접근

dp, 가장 긴 연속 수열 구하는 문제였다.
3 7 5 2 6 1 4
3 4 2 1
2 3 4 5 6 7 1
이렇게 작은 예들을 한번 씩 해보면 규칙을 찾을 수 있었다.

코드 구현(c++)

#include <iostream>
#include <algorithm>

using namespace std;

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int N;
    int nums[201];
    int dp[201];
    cin >> N;
    for(int i = 0 ; i < N ; i++){
        cin >> nums[i];
    }
    int maxNum = -1;
    for(int i = 0 ; i < N ; i++){
        dp[i] = 1;
        for(int j = i - 1 ; j >= 0 ; j--){
            if(nums[j] < nums[i]) 
            {
                dp[i] = max(dp[i] , dp[j] + 1);
            }
        }
        maxNum = max(maxNum, dp[i]);
    }
    cout << N - maxNum << "\n";
}