[백준 11722번 / C++] 가장 긴 감소하는 부분 수열

dp 배열을 활용해서 풀면된다. 

 

#접근방법 

 

본인은 증가수열이 매우 익숙해서 reverse 함수를 통해서 벡터의 순서를 바꿔주고 

LIS(최장증가수열)를 통해 문제를 풀었다. 

 

dp 배열 1로 초기화, v 배열 데이터값 저장. 

1. v 배열 인덱스 1부터 n-1까지 돌면서 dp를 확인한다. 
2. 인덱스 i에 위치한 v 벡터의 데이터값과 인덱스값이 j (for (j< i))인 데이터값과 비교한다. 
3. 인덱스 i에 위치한 데이터값이 인덱스 j에 위치한 데이터값보다 클 경우 dp[j]+1의 값과 dp[i] 값을 비교해서 큰 값으로 갱신해간다. 
4. 이후 dp에 세팅된 값중 가장 큰값을 정답으로 출력한다.  

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

int main() {
	int n; cin >> n;
	vector<int> v;
	for (int i = 0; i < n; i++) {
		int a; cin >> a;
		v.push_back(a);
	}
	reverse(v.begin(), v.end());
	vector <int> dp(n, 1);
	int max_n = 1;
	for (int i = 1; i < n; i++) {
		for (int j = i - 1; j >= 0; j--) {
			if (v[i] > v[j]) {
				dp[i] = max(dp[j] + 1, dp[i]);
				
			}
		}
		max_n = max(dp[i], max_n);
	}
	cout << max_n;
}

 

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