🖊️ 문제

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

---

🖊️ 풀이

dp문제니까 점화식을 세워야 한다.

예시 수열 = {10, 20, 10, 30, 20, 50}

가장 작은 부분 수열은 자기 자신만을 포함하고 있는 것이니까 일단 최소 길이 = 1이다

현재까지의 가장 긴 증가하는 부분 수열의 길이를 dp에 저장하자.

i번째까지의 가장 긴 증가하는 부분 수열의 길이를 구하기 위해서는, i번째까지 중 본인보다 작은 수를 가진 원소들의 개수를 센다.
그리고 그 중 가장 큰 것을 세면 된다.

i번째의 값이 이전 값보다

i번째 값에 대해, i 이전 수열의 값들이 더 작다면 해당 수열까지의 ~길이의 합에 본인이 추가되니까 +1 된다.
이걸 점화식으로 세우면

arr[i] > arr[j]일 때
dp[i] = max(dp[i], dp[j] + 1)

반드시 마지막 수열에서의 dp값이 최대일리는 없으니, 매 번 최대값을 추출해주면 된다.

점화식 세우기가 어려웠던 문제 ...

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

int arr[1001];
int dp[1001];

int main()
{
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(0);

	int n;
	cin >> n;

	int num;
	int result = 0;
	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);
			}
		}
		result = max(result, dp[i]);
	}

	cout << result << endl;
}