문제

문제 링크

해설

• 증가하는 부분 수열 (LIS)은 DP를 이용한 방법(O(N²))과 이분탐색을 이용한 방법 (O(NlogN))이 있지만, 감소하는 부분 수열은 DP 밖에는 방법이 없는 것 같습니다.
• 1로 초기화된 dp 배열을 만듭니다.
  • 왜냐하면, 모두 자기자신을 부분수열로 하기 때문입니다.
  • 그러므로, dp 배열의 초깃값은 길이가 1이라는 뜻에서 1입니다.
• 1번 인덱스부터 마지막 인덱스까지 진행하며 자신의 뒤쪽에 있는 요소와 자신을 비교하면서 감소하는지 여부를 확인합니다.
• 만일 감소한다면, 해당 요소의 dp값과 자신의 dp값을 비교하며 더 큰쪽을 저장합니다.
• std::max_element() STL 함수를 이용하면 간단하게 dp 배열의 최댓값을 출력할 수 있습니다. 이것이 LDS의 최장길이입니다.

코드

#include <bits/stdc++.h>
using namespace std;

int main() {
	cin.tie(0)->sync_with_stdio(0);
	
	int N;
	cin >> N;
	vector<int> arr(N);
	for (int i = 0; i < N; ++i) cin >> arr[i];
	
	vector<int> dp(N, 1);
	for (int i = 1; i < N; ++i)
		for (int j = 0; j < i; ++j)
			if (arr[j] > arr[i]) dp[i] = max(dp[i], dp[j] + 1);
	cout << *max_element(begin(dp), end(dp));
}

소스코드 링크

결과