BOJ 11053 (가장 긴 증가하는 부분 수열)

• 문제
  수열 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의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

#include<iostream>
#include<algorithm>
using namespace std;
int N;
int arr[1001];
int temp[1001];

void fast_io()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
}

void check()
{
	int cnt = 0;
	for (int i = 1; i <= N; i++)
	{
		temp[i] = 1;
		for (int j = i - 1; j > 0; j--)
		{
			if (arr[i] > arr[j])
			{
				temp[i] = max(temp[i], temp[j] + 1);
			}
		}
		cnt = max(temp[i], cnt);
	}
	cout << cnt;
}

int main()
{
	fast_io();
	cin >> N;
	for (int i = 1; i <= N; i++)
	{
		int num; cin >> num;
		arr[i] = num;
	}
	check();
	return 0;
}

  수열 중 원소가 가장 큰 값이 맨 뒤에 위치할 때 가장 긴 증가하는 부분 수열을 얻게 된다. 앞쪽부터 살펴보면 10일때는 1 20일 때는 {10,20} 구성으로 길이 2가 되고
두 번째 10에서는 {10}으로 1이된다. 30에 가면 {10,20,30}으로 길이 3을 얻는데 이는 20일때에서 현재 30을 포함한 2+1로 길이 3이 되는 것이다.
  즉 이전의 최대 길이에서 자기 자신 포함 1 증가시킨 값을 찾으면 된다 => 다이나믹 프로그래밍 기법으로 값을 보존하며 문제에서 원하는 최적의 값을 찾으면 문제를 해결할 수 있다.

시간 복잡도 : O(N^2)