[백준 BOJ][C++]11053번 가장 긴 증가하는 부분 수열 풀이: DP

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

 

 

 이 문제는 Dynamic Programming, DP를 사용하여 해결할 수 있습니다. 

 

 dp[n]을 수열 A에서 n번째 숫자까지의 증가하는 부분 수열의 길이라고 할 수 있습니다. 

 

 예제 수열인 10 20 10 30 20 50으로 진행과정을 보겠습니다. 

 

 수열의 첫 번째 원소인 10 먼저 보겠습니다. 첫 번째 원소까지의 증가하는 부분 수열의 길이는 당연히 1이겠죠?

dp[n]	1
A[n]	10	20	10	30	20	50

 

 두 번째 원소인 20을 보겠습니다. dp[2]는 어떻게 될까요? 두 번째 숫자까지 증가하는 부분 수열은 {10, 20}이고 그 길이는 2 입니다. 

dp[n]	1	2
A[n]	10	20	10	30	20	50

 

 세 번째 원소 10은 첫 번째, 두 번째 원소인 10과 20보다 크지 않습니다. 때문에 dp[3]은 1이 되겠죠?

dp[n]	1	2	1
A[n]	10	20	10	30	20	50

 

 4, 5, 6 번째 원소도 동일한 방법으로 다음과 같이 나타낼 수 있습니다. 

dp[n]	1	2	1	3	2	4
A[n]	10	20	10	30	20	50

 

 

 즉, n번째 원소까지의 증가하는 부분 수열의 최대 길이는 1번째부터 n-1번째 원소 중 n번째 원소보다 작은 원소들 중 최대 dp값 + 1 입니다. 

 

 

#include<iostream>
#include<vector>
#include<algorithm>
#include<cstdlib>

using namespace std;

vector<int> dp(1001, 1);
int arr[1001];

int main(void) {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int ans = 0;
	int n;

	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}

	for (int i = 0; i < n; i++) {
		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;

	return 0;
}