백준 2631번 줄세우기

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

http://jaimemin.tistory.com/430와 비슷하게 LIS를 떠올리는 것이 핵심인 문제였습니다.

결국 어린이들 중 정렬이 안되있는 어린이들만 정렬하면 되므로 (총 어린이 수 - 최대 증가 순열)을 구하면 되는 문제였습니다.

#include <iostream>

#include <algorithm>

#include <cstring> //memset

using namespace std;

 

const int MAX = 200;

 

int N;

int arr[MAX];

int cache[MAX + 1];

 

int LIS(int start) //Longest Increasing Sequence

{

        int &result = cache[start + 1];

        if (result != -1)

               return result;

        result = 0;

        for (int next = start + 1; next < N; next++)

               if (start == -1 || arr[start] < arr[next])

               {

                       int candidate = 1 + LIS(next);

                       if (result < candidate)

                              result = candidate;

               }

        return result;

}

 

int main(void)

{

        cin >> N;

        if (N<2 || N>MAX)

               exit(-1);

 

        for (int i = 0; i < N; i++)

               cin >> arr[i];

 

        memset(cache, -1, sizeof(cache));

        //정렬되어있는 학생들은 안 움직여도 된다

        cout << N - LIS(-1) << endl;

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~