[백준] 11053번 가장 긴 증가하는 부분 수열 [C++]

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

---

문제

 

 

---

접근 방법

예를 들어 

1, 2 , 5 , 4 

라는 수열이 있다고 하면, 원소가 1개일 때 가장 긴 부분수열은 1이다.

이를 DP[1] = 1 이라고 정리를 한다.

원소가 2개일 때는 가장 긴 부분수열은 1,2이다. 이는 2번째 원소인 2를 1뒤에 붙힌 것이며, 이를 DP[2]=DP[1]+1=2 이라고 표현 할 수 있다.

원소가 3개일 때 가장 긴 부분수열은 1,2,5이다. 이는 3번째 원소를 1,2 뒤에 분힌 것이다.

이는 두가지 경우중에 더 큰 경우를 선택한 것인데,

{1} 뒤에 5을 붙힌 경우 or {1,2}뒤에 5을 붙힌 경우 중 두번째를 선택한 것이다.

즉 DP[3]=DP[2]+1이라고 할 수 있다.

마지막으로 원소가 4개 일 때를 보면, 4를 어떤 수열 뒤에 붙혀야 하는지가 관건인데,

{1} (dp[1]) 과 {1,2} (dp[2]) 뒤에는 붙힐 수 있지만, {1,2,5}(dp[3]) 뒤에 4를 붙히면 증가하는 수열이 되지 않는다.

즉 , 현재 원소보다 더 작은 경우의 뒤에만 붙힐 수 있게 되고, 이를 점화식으로 나타낸다면

N번째 원소가 M번쨰 원소보다 큰 경우에는

DP[N]=max(DP[M])+1 이 된다.

---

코드

#include<iostream>
using namespace std;
int arr[1001];
int dp[1001];
int main() {
	ios_base::sync_with_stdio(false);
	int n;
	cin >> n;
	int ans = 0;
	for (int i = 1; i <= n; i++) {
		cin >> arr[i];
		dp[i] = 1;
		for (int j = 1; j < i; j++) {
			if (arr[i] > arr[j]) {
				dp[i] = max(dp[i], dp[j] + 1);
			}
		}
		ans = max(ans, dp[i]);
	}
	cout << ans;
}

---

다이나믹 프로그래밍 중 굉장히 well-known한 문제라고 들었고, 확실히 이 문제와 비슷한 유형의 문제도 많은 것 같다.