백준 11722번: 가장 긴 감소하는 부분 수열

백준 온라인 저지(BOJ) 11722번 문제

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

1. 문제 요약

수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열의 길이를 구하기.

2. 알고리즘

다이나믹 프로그래밍을 사용하여 $O(n^2)$의 시간에 구하는 방법은 생각해보았다.

감소하는 부분 수열이 예를 들어서 {30, 20, 10}일 때, 이는 30 + {20, 10}이라서 길이가 2 + 1이 된 것이라 생각하자.

맨 뒤는 길이 1로 저장하고,

그 이후는 그 성분을 포함시켰을 때 감소하는 수열이 되는 값들의 길이를 훑고, 그 최댓값에 1을 더한 뒤 저장하면 되겠다.

말로 설명하기 약간 어려워서 보충

 {10, 30, 10, 20, 20, 10}

                           1

                      2   1 (20보다 작은 값 10)

                  2   2   1 (20보다 작은 값 10)

             1   2   2   1 (10보다 작은 값 없음)

        3   1   2   2   1 (30보다 작은 값 20, 20, 그 중 최대 길이 2)

   1   3   1   2   2   1 (10보다 작은 값 없음)

맨 마지막으로 전체를 쭉 훑으며 최댓값을 출력하면 끝.

3. 코드

#include <iostream>

int main() {
	int N;
	scanf("%d", &N);
	int* arr = new int[N];
	int* len = new int[N];

	for (int i = 0; i < N; ++i) {
		scanf("%d", arr + i);
	}

	for (int i = N - 1; i >= 0; --i) {
		int max = 0;
		for (int j = i + 1; j < N; ++j) {
			if (arr[j] < arr[i] && len[j] > max) max = len[j];
		}
		len[i] = max + 1;
	}
	int max = 0;
	for (int i = 0; i < N; ++i) {
		if (max < len[i]) max = len[i];
	}

	printf("%d\n", max);

	delete[] arr;
	delete[] len;

	return 0;
}