Dynamic Programming(LIS)(Baekjoon11722)

LIS 알고리즘을 통해 푸는 문제이다.

동적할당법을 통해 풀게되는데 문제에 있는 예제를 통해 살펴보자.

먼저 A = [10,30,10,20,20,10] 에 대응하는 가장 긴 수열의 길이를 저장하는 memo배열을 할당한다.

A[1] 은 첫번째 배열이며 최장 부분수열의 길이도 1이 된다.

(편의상 A[0]이 아닌 A[1]이 첫번째 배열이라고 가정한다.)

A	10	30	10	20	20	10
memo	1

다음으로 A[2]는 30이며 먼저 기본적으로 가지는 수열의 길이인 1을 먼저 할당한다.

그 후 앞에 있는 배열을 검사한다. 

감소하는 수열의 길이를 구하는데 앞에있는 A[1]은 A[2]보다 작으므로 

A[2]까지 최장 부분수열의 길이는 1에서 변화없이 끝나게 된다.

A	10	30	10	20	20	10
memo	1	1	2

다음으로 A[3]은 10이며 역시 1이 할당되고, 앞에 있는 A배열중에 10보다 큰 수는 30밖에 없으며

memo[2]에 1을 더한 값이 2 이므로 memo[3]에는 2를 할당한다.

A	10	30	10	20	20	10
memo	1	1	2

다음은 A[4]이며 기본 1을 할당 한 후 앞의 배열을 천천히 살펴보면 30이라는 A[4]보다 큰 숫자를 찾을 수 있으며 30까지의 부분수열의 길이에다 1을 더한 값이 A[4]까지의 최장 부분수열의 길이가 되므로

memo[4]에 할당한다. 

이런식으로 마지막까지 구하게 되는데 

만약 A[i]보다 큰 숫자가 1개 이상이 있다면 그에 해당하는 memo배열을 모두 검사해

그중에 가장 큰 memo에 1을 더한 값을 memo[i]에 할당하면 된다.

A	10	30	10	20	20	10
memo	1	1	2	2	2	3

아래는 코드를 통해 이 과정을 구현한 것이다.

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

int A[1001];
int memo[1001];

int main()
{
	int n;
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) scanf("%d", &A[i]);
	int max = 1;

	for (int i = 1; i <= n; i++) {
		memo[i] = 1;
		for (int j = i; j >= 1; j--) {
			if (A[i] < A[j] && memo[i] < memo[j] + 1) {
				memo[i] = memo[j] + 1;
			}
		}
		if (max < memo[i]) max = memo[i];
	}
	printf("%d\n", max);
}