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

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

 

일단 자기 자신만 있어도 하나의 수열이기 때문에 dp배열의 값을 전부 1로 초기화해주었다.

그리고 2중 for문을 사용했다. 첫 번째 for문은 i = 0부터 n-1까지 순차적으로 탐색하는 것이고, 두 번째 for문은 j =0부터

i - 1까지 v[j]의 값이 v[i]보다 작다면 감소하는 부분 수열이기 때문에 이전 dp[i]와 비교해서 dp[j]+1가 크다면 갱신해주는 방식으로 문제를 해결하였다.

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>

using namespace std;
using ll = long long;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n;
	cin >> n;
	vector<int> v(n);
	vector<int> dp(n, 1);
	for (int i = 0; i < n; i++) {
		cin >> v[i];
	}
	int ans = 1;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < i; j++) {
			if (v[i] < v[j]) {
				dp[i] = max(dp[i], dp[j] + 1);
			}
			ans = max(ans, dp[i]);
		}
	}
	cout << ans;
};