백준 2631 c++ : DP, LIS

#include <iostream>
#include <vector>

using namespace std;

void input_data(int* N, vector<int>& KOI_kindergarten) {
	cout << "input_data()\n";
	int i, num;

	cin >> *N;
	for (i = 0; i < *N; i++) {
		cin >> num;
		KOI_kindergarten.push_back(num);
	}

	return;
}

int find_answer(int N, vector <int>& KOI_kindergarten) {
	cout << "find_answer()\n";
	int answer = 0, max_count = 0;
	int i, j; 
	vector<int> DP(N + 1, 1);

	//최장 증가 부분 수열 -> LIS
	//가장 큰 증가하는 수열을 찾아서(부분적으로 정렬이 된 상태) 
	//-> 그 부분을 제외한 수들을 재배치하면 최소 비용으로 정렬 가능
	for (i = 1; i <= N; i++) {
		for (j = 1; j <= i; j++) {
			if (KOI_kindergarten[j - 1] < KOI_kindergarten[i - 1]) {
				DP[i] = max(DP[i] , DP[j] + 1);
			}
			cout << DP[j] << " ";
		}
		max_count = max(max_count, DP[i]);
		cout << " / max : " << max_count << "\n";
	}
	answer = N - max_count;

	return answer;
}

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

	int N;
	vector<int> KOI_kindergarten;

	input_data(&N, KOI_kindergarten);
	cout << find_answer(N, KOI_kindergarten) << "\n";

	return 0;
}