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

문제 링크

https://www.acmicpc.net/problem/11722

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

 

11053번 가장 긴 증가하는 부분 수열의 반대로 현재 위치가 이전 위치보다 작은 경우를 구해주면 됩니다.

 

 

구현 코드

 

	#include <iostream>
	#include <algorithm>
	#define endl '\n'
	#define fastio cin.sync_with_stdio(false); cin.tie(nullptr)
	using namespace std;
	int main(){
	fastio;
	int n;
	int arr[1001];
	int dp[1001];
	int ans=0;
	cin >> n;
	for(int i=0;i<n;i++){
	cin >> arr[i];
	}
	for(int i=0;i<n;i++){
	dp[i] = 1;
	for(int j=0;j<i;j++){
	if(arr[i] < arr[j]){
	dp[i] = max(dp[i],dp[j]+1);
	}
	}
	ans = max(ans,dp[i]);
	}
	cout << ans << endl;
	return 0;
	}

view raw 11722.cpp hosted with ❤ by GitHub