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

 

다이나믹 프로그래밍 문제입니다.

N명의 아이들을 순서대로 정렬 시키는 문제입니다.

LIS알고리즘으로 문제를 풀었습니다.

가장 잘 정렬되어있는 곳을 찾으면 나머지 학생들은 전부 이동해야하므로

최대길이 수열을 구하고 전체 인원에서 그 길이만큼을 빼면 결과가 나옵니다.

 

#include <iostream>
using namespace std; 

int child[200];    // 아이들 위치
int check[200];     // LIS확인

void init(int cycle) // 초기화
{ 
    for (int i = 0; i < cycle; ++i) { 
        check[i] = 1; 
    } 
} 

int main(int argc, char *argv[]) 
{ 
    int cycle; // 반복 횟수
    cin >> cycle; 
    init(cycle); 
    for (int i = 0; i < cycle; ++i) { 
        cin >> child[i]; 
    } 
    for (int i = 0; i < cycle; ++i) { 
        for (int j = i - 1; j >= 0; --j) { 
            if (check[i] <= check[j] && child[i] > child[j]) {  // 전 배열들을 검사해서 현재배열보다 수열이 크면서
                check[i] = check[j] + 1;                            // 값이 작으면 그 수열 +1한 값을 현재 배열에 삽입
            } 
        } 
    } 
    int max = 0; 
    for (int i = 0; i < cycle; ++i) { 
        if (max < check[i]) { 
            max = check[i]; 
        } 
    } 
    cout << cycle - max << endl; 
    return 0; 
}