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

LIS 문제이다. 

 

수열이 만약 "3, 5, 8, 10, 1, 4" 으로 주어졌다면 직관적으로 1과 4를 앞에다가 놓으면 되는거 아닌가? 

라는 생각이 들면 된다. 그렇다면 그 기준이 뭘까? 

 

위의 수열에서 보면 3 < 5 < 8 < 10 > 1 < 4  이런식의 부등호가 될텐데, 

여기서 최장 증가 부분 수열은 "3, 5, 8, 10" 이다. 

 

즉, 가장 크게 증가 하는 연속된 부분 수열은 위치를 고정시키고 그 수열에 포함되지 않는 숫자들을

삽입해서 정렬한다고 생각하면 이해될 것이다. 

 

아래 코드를 보고 이해해보기를 권한다. 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std; 
 

int main() {
	int n; cin >> n; 
	vector <int> v(n+1);
	for (int i = 1; i <= n; i++) {
		cin >> v[i]; 
	}
	int result = 0; 
	vector <int> dp(n + 1, 1); 
	for (int i = 2; i <= n; i++) {
		int max_n=1; 
		for (int j = i - 1; j >= 1; j--) {
			if (v[i] > v[j]) {
				max_n = max(max_n, dp[j] + 1); 
			}
		}
		dp[i] = max_n;
		result = max(result, dp[i]); 
	}
	cout << n - result; 

}

 

2631번: 줄세우기