[백준] 11722-가장 긴 감소하는 부분 수열(C++)

문제링크:https://www.acmicpc.net/problem/11722

11722번: 가장 긴 감소하는 부분 수열

 

전형적인 LIS 문제였습니다. 

LIS 개념을 아신다면 어렵지 않은 문제였습니다.

그나마 주의해야 할 점은 이전 dp값을 전부 확인해봐야한다는 것입니다. 

바로 이전의 자신보다 큰값만 비교할 경우 예외가 발생합니다. 

 

Ex) 5

     10 5 4 6 3

 

정답코드입니다. 화이팅 :)

#include <iostream>
using namespace std;
int dp[1001] = { 0 };
int arr[1001] = { 0 };
int n,num,result =0;
int main() {
	cin >> n;

	for (int i = 0; i < n; i++) {
		int maxed = 0;
		cin >> arr[i];
		for (int j = 0; j < i; j++) {
			if (arr[i] < arr[j] && maxed < dp[j])
				maxed = dp[j];
		}
		dp[i] = maxed + 1;
	}
	
	for (int i = 0; i < n; i++) {
		if (result < dp[i]) result = dp[i];
	}
	cout << result << endl;
}