이코테 DP : 병사 배치하기 [C++]

 

이문제는 가장 긴 증가하는 부분수열(LIS)을 푸는 방식과 매우 비슷하다.

다만 여기선 가장 긴 감소하는 부분 수열을 찾는 문제이며 최댓값을 찾아내는 것이고 순서는 상관없기 때문에 

입력받은 값을 reverse시켜서 가장 긴 증가하는 부분 수열처럼 처리하면 된다. 

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

int n;
vector<int> v;


int main(void) {
	cin >> n;
	for (int i = 0; i < n; i++) {
		int x; 
		cin >> x;
		v.push_back(x);
	}
	// 순서를 뒤집어 '최장 증가 부분 수열' 문제로 변환
	reverse(v.begin(), v.end());
	// 다이나믹 프로그래밍을 위한 1차원 DP 테이블 초기화
	int dp[2000];
	for (int i = 0; i < n; i++)	dp[i] = 1;
	// 가장 긴 증가하는 부분 수열(LIS) 알고리즘 수행
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < i; j++) {
			if (v[j] < v[i]) dp[i] = max(dp[i], dp[j] + 1);
		}
	}
	int maxValue = 0;
	// dp중 가장 큰 수를 찾아서 병사의 수에서 빼기
	for (int i = 0; i < n; i++) {
		maxValue = max(maxValue, dp[i]);
	}
	cout << n - maxValue << '\n';
}