[C++] BOJ 2631 줄세우기

문제 출처

백준 온라인 저지

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

2631번: 줄세우기

 

문제 

 

 

입 / 출력

 

풀이

아이들을 번호 순서대로 배치하기 위해서 최소로 옮겨야 하는 수는

이미 번호 순서대로 정렬되어있는 아이들을 제외한 아이들을 옮겨야 하는 수와 같은 의미를 가진다

 가장 긴 부분 수열의 길이를 구하고, 그 값을 전체 아이의 수에서 빼주면 값을 구할 수 있다

 

코드

#include <algorithm>
#include <iostream>

using namespace std;

const int MAX = 201;
int n, result = 0;
int children[MAX], dp[MAX];

int main() {
  cin >> n;
  for (int i = 0; i < n; i++) {
    cin >> children[i];
    dp[i] = 1;
  }

  for (int i = 0; i < n; i++) {
    for (int j = 0; j < i; j++)
      if (children[j] < children[i]) {
        dp[i] = max(dp[i], dp[j] + 1);
      }
    result = max(result, dp[i]);
  }
  cout << n - result << "\n";
}