백준 2631 줄세우기 LIS 개념 다이나믹 프로그래밍

줄세우기 문제는

 

3 7 5 2 6 1 4   라는 수열이 있으면 숫자를 최소로 움직여  정렬 상태로 바꾸는 문제이다.

(1 2 3 4 5 6 7)

dp문제로 분류되어 있지만 바로  DP를 사용하기에는 감이 잡히지 않았다.

 

이런 문제를 LIS 문제라고 하는데, 

위 문제를 잘 생각해보면 모든 숫자는 한번 움직이기만하면 원하는 위치에 딱 놓을 수 있다.

N개 문제가 있다면 N번 안에 무조건 해결 가능하다.  어쩌면 어떤 숫자들은 가만히 있어도 된다.

즉, 최대한 많은 숫자들이 움직이지 않아도 될 수록 좋다는 것 !!!

그리고 건들이지 않아도 되는 숫자들은 , 이미 각 숫자들이 오름차 순으로 있다는 것

 

그렇다면 우리는 이미 오름차순으로 정렬되어있는 가장 긴 순열 길이를 찾으면 된다.

 

위 문제에서는  3 7 5 2 6 1 4    3 ,5 ,6 세개가 가장 긴 순열이도

 

이 숫자를 제외하고 나머지 숫자만 이동시킨다면, 그것이 가장 최소이다.

 

즉 정답은 7 - 3 = 4

 

최대 순열길이를 구하기 위해서, DP를 사용하기 때문에 dp문제로 분류된거 같다..

 

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int N;
vector<int> number;
vector<int> maxlen;

//가장 긴수열을 찾기위한 dp
int dp(int src) {
	if (maxlen[src]) return maxlen[src];
	if (src == N - 1) return 1;
	int mmax = 0;
	for (int i = src + 1; i < N; i++) {
		if (number[src] < number[i])
			mmax = max(mmax,dp(i));
	}
	return maxlen[src] = mmax + 1;
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> N;
	number.resize(N);
	maxlen = vector<int>(N, 0);


	//LIS 문제
	// 정렬 최소 횟수 문제는
	// 이미 정렬되어있는 가장 긴 수열 고정한채
	// 나머지 개수를 움직이면된다.
	// 정답은 곧 가장 긴 수열에 포함되지 않는 객체의 개수
	// N - LIS  이다.
	for (int i = 0; i < N; i++)
		cin >> number[i];

	int mmax = 0;

	for (int i = 0; i < N; i++)
		mmax = max(mmax, dp(i));

	cout << N - mmax;

}