줄세우기(DP)

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

2631번: 줄세우기

 

입력받은 순서에서 최장 증가 부분 수열(LIS)를 찾으면 되는 문제다.

LIS은 수열의 부분 수열 중 각 원소가 이전 원소보다 큰(오름차순) 수열 중 그 길이가 가장 긴 수열을 의미한다.

최장 증가 부분 수열에 속하는 숫자를 제외한 나머지를 이동하는 것이 문제의 해답이다.

 

LIS은 다이나믹 프로그래밍 기법으로 찾을 수 있다.

DP에 저장되어야 하는 정보는 그 지점까지의 LIS의 길이를 저장해주고

탐색할때 현재 위치보다 낮은 위치의 수를 전부 탐색하여 '낮은 위치의 수 < 현재 위치의 수'를 만족한다면

현재 지점의 LIS = max(현재 지점의 LIS, 특정 지점의 LIS + 1)으로 나타낼 수 있다.

현재 지점의 LIS 디폴트 값은 1이다.

이렇게 탐색한 LIS중 최댓값을 전체 인원수에서 빼면 된다.

 

#include <iostream>
using namespace std;

int line[200];
int DP[200] = { 0, };

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int count;
	cin >> count;
	for (int i = 0; i < count; i++)
	{
		cin >> line[i];
	}

	int ret = 0;
	DP[0] = 1;
	for (int i = 1; i < count; i++)
	{
		DP[i] = 1;
		for (int j = 0; j < i; j++)
		{
			if (line[j] < line[i])
			{
				DP[i] = max(DP[i], DP[j] + 1);
				ret = max(ret, DP[i]);
			}
		}
	}

	cout << count - ret << '\n';
}