[백준] 2631번 줄세우기

문제

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

풀이과정

어제 푼 문제와 똑같이 LIS(최장 부분 증가 수열)에 관한 문제이다. 아직 LIS 개념을 정확히 모르겠다. 더 찾아봐야겠다.

DP[i] 를 i번째 원소를 끝으로 가지는 배열이 가질 수 있는 최장 부분 증가 수열의 길이라고 할 때, 정답을 출력하려면 입력 배열의 총 길이에서 최장 부분 증가 수열의 길이를 빼면 된다.

소스코드

#include <iostream>
#pragma warning(disable:4996)
 
int children[201], DP[201];
 
int main()
{
    int N,max=0;
 
    scanf("%d", &N);
 
    for (int i = 1; i <= N; i++)
    {
        scanf("%d", &children[i]);
    }
 
    for (int i = 1; i <= N; i++)
    {
        DP[i] = 1;
        for (int j = 1; j < i; j++)
        {
            if (children[j] < children[i] && DP[i] < DP[j] + 1)
                DP[i]++;
            if (max < DP[i]) max = DP[i];
        }
    }
 
    printf("%d", N-max);
 
    return 0;
}