[C++][백준 2631] 줄세우기

[문제]

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

2631번: 줄세우기

[문제 풀이]

어려워보이지만 생각보다 간단하게 맞출 수 있는 문제다. 문제에 낚이지 말고 해당 결과값을 만들기 위해서 뭐가 필요한지를 잘 생각하자!

 

만일 살짝 고민해봐도 모르겠다면 가장 긴 증가하는 부분 수열 해당 문제를 한번 보고 오자.

 

만일 보고 왔다면 아마도 감이 왔을것이다.

그래도 모르겠다면 이런식으로 생각해보자. 증가하는 부분 수열이라는 말은 반대로 말하면 해당 부분들을 제외하고 움직이면 오름차순대로 줄을 세울 수 있다.

 

즉 N - 가장 긴증가하는 부분 수열의 길이를 빼면 해당 문제의 답이 나올 수 있다.

 

i를 1부터 순서대로 가게 만들고 j를 i 이하까지 계속 돌리자.(14~16)

만일 i번째 수보다 j가 작다면(17)

또한 해당 자리수의 증가하는 부분 수열의 길이가 더 크다면 해당 부분 수열의 길이보다 증가시켜주자.(18)

[코드]

#include<iostream>
#include<algorithm>
#define endl "\n"
 
using namespace std;
 
int cares[201];
int DP[201];
 
void solve(int n){
 
    int Max = 0;
    DP[0] =1;
    for(int i = 1;i<n;i++){
        DP[i] = 1;
        for(int j = 0;j<i;j++){
            if(cares[i]>cares[j]){
                if(DP[j] >= DP[i]){
                    DP[i] = DP[j] +1;
                }
                else{
                    continue;
                }
            }
        }
        if(Max<DP[i]){
            Max = DP[i];
        }
    }
 
    cout<<n- Max<<endl;
 
    return;
}
 
int main(){
    int n;
    cin>>n;
    for(int i = 0;i<n;i++){
        cin>>cares[i];
    }
    solve(n);
    return 0;
}