백준 / 다이나믹 프로그래밍 / 11053번 / 가장 긴 증가하는 부분 수열 / C++

문제

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)

출력

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

예제 입력 1 

6

10 20 10 30 20 50

예제 출력 1 

4

 

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

const int N = 1e3 + 1;
int arr[N];
int dp[N];

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	int n;
	int result = 1;
	cin >> n;
	
	for(int i=1; i<=n; i++) {
		cin >> arr[i];
		int tmp = 0;
		
		for(int j=1; j<=i; j++) {
			if(arr[i] > arr[j]) {
				tmp = max(tmp, dp[j]);
			}
		}
		dp[i] = tmp + 1;
		result = max(result, dp[i]);
	}
	
	cout << result << '\n';
	
	return 0;
}

---

알고리즘 자체가 DP(Dynamic Programming)을 접하지 얼마 안되서 그러는지는 몰라도 이번은 도저히 모르겠어서

검색을 했다.

 

일단 arr 배열에 입력받은 값을 저장한다.

그리고 dp 배열은 arr의 입력받은 값들의 인덱스까지의 수들이 이루는 수열의 최대 길이를 나타낸다.

예를 들어 입력받은 값이 1,2,5,2,3 이라면 아래와 같이 된다.

 

dp[1] = 1 (1)

dp[2] = 2 (1,2)

dp[3] = 3 (1,2,5)

dp[4] = 3 (1,2,5)

dp[5] = 3 (1,2,5)

 

그리고 배열을 2중 반복문을 돌면서 현재 인덱스가 i라면 j를 i까지 반복시켜주는데 

만약 arr[i] > arr[j]라면 tmp변수에 현재의 tmp값과 dp[j]값을 비교해서 최댓값으로 할당해준다.

 

그러면 한번더 반복하게 될시 만약 전 반복문에서 dp[j]가 tmp보다 더커서 tmp에 할당되었을 경우는 어떤경우냐면,

위에서 언급한 예시로 살펴보자면 처음에 tmp에 dp[1], 즉 1이 할당되었고 다음으로 넘어가서 dp[2]가 2이므로 

더 큰값으로 재할당 해주는것이다.

 

그러고나서 2중반복문의 안쪽 반복문을 빠져나오게 되면 dp[i]에 tmp + 1을 해주는데,

+1을 해주는 이유는 뭐냐면 수열에 자기자신도 포함되므로 +1을 해주는것이다.

 

그 후 result와 dp[i]를 비교해서 result에 값을 할당해준뒤 모든 반복문을 마치고 result를 출력해준다.

result를 1로 초기화한 이유는 어떤 수든 자기자신만으로 길이 1의 수열을 가질 수 있기 때문이다.