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

문제 링크

2631번: 줄세우기

 

풀이 ) DP - LIS

  LIS를 활용한 문제이다. 옮겨지는 아이들을 주목해서 입력 예시인 3 7 5 2 6 1 4 에서 옮겨지는 아이를 다른 색으로 표시하면 3 7 5 2 6 1 4 가 된다.

  이 때 옮겨지는 아이, 즉 붉은색으로 표시된 아이들을 제외하고는 가장 긴 부분 수열을 만족하는 것을 알 수 있다. 가장 긴 부분 수열에서 해당하지 않는 아이만 옮겨주면 된다는 뜻이다.

 

#include <cstdio>
#include <algorithm>
using namespace std;

int main(void)
{
  int n, arr[201] = {0, }, memo[201], move = 0;
  scanf("%d", &n);
  for(int i = 0; i < n; ++i)
    scanf("%d", arr+i);

  fill(memo, memo+sizeof(memo)/sizeof(int), 1);
  for(int i = 0; i < n; ++i){
    for(int j = 0; j < i; ++j)
      if(arr[i] > arr[j])
        memo[i] = max(memo[i], memo[j]+1);
    move = max(move, memo[i]);
  }
  printf("%d\n", n-move);
}