[백준] C++ 18353번 병사 배치하기 실버2 - DP

문제 : https://www.acmicpc.net/problem/18353

접근 방법

1. 대표적인 LIS 문제이다.

• LIS란? Longest Increasing Subsequence의 줄임말로 최장 증가 부분 수열이라는 뜻이다. 이게 무슨 어려운 말이냐,,?
• 한 배열이 있을 때 그 배열에서 값이 계속 증가하는 부분 배열 중 가장 긴 것을 말한다.
  ex) [1,3,2,7,8,6]가 있을 때
  [1,7], [3,7,8], [1,3,7,8] 등의 오름차순 부분 배열이 나올텐데 그 중 가잔 긴 값인 [1,3,7,8]이 답이 되는 것이다.

풀이

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

int N, a;
vector<int >v;

int main() {
	cin >> N;

	for (int i = 0; i < N; i++) {
		cin >> a;
		v.push_back(a);
	}
	reverse(v.begin(), v.end());

	int dp[2000];
	for (int i = 0; i < N; i++)
		dp[i] = 1;

	for (int i = 1; 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;

	for (int i = 0; i < N; i++) {
		maxValue = max(maxValue, dp[i]);
	}
	cout << N - maxValue << "\n";
}