[백준] 11053 가장 긴 증가하는 부분 수열 (LIS) / DP (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의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

#include <iostream>
using namespace std;

// dy의 정의는 각 수열의 해당위치에서 만들 수 있는 가장 긴 부분 증가 수열의 길이
int dy[1001];
int arr[1001];

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	int N, ans;
	cin >> N;

	for (int i = 1; i <= N; i++)
	{
		cin >> arr[i];
	}
		
	// 기본적인 개념은 현재 위치가 부분 증가 수열의 마지막 숫자라고 생각하고,
	// 그 위치에서 만들 수 있는 가장 긴 부분 증가수열의 길이를 dy에 기록한다.
	// 첫 번째는 당연히 길이가 1
	dy[1] = 1;

	for (int i = 2; i <= N; i++)
	{
		int max = 0;
		for (int j = i - 1; j > 0; j--)
		{
			// 앞으로 하나씩 내려가면서 최대값을 체크한다.
			// 현재 위치의 값보다 작은 수이고, 현재 최대값보다 클 때 갱신해준다.
			if (arr[j] < arr[i] && max < dy[j])
			{
				max = dy[j];
			}
		}
		dy[i] = max + 1;
	}

	ans = -1;

	for (int i = 1; i <= N; i++)
	{
		if (dy[i] > ans)
		{
			ans = dy[i];
		}
	}
	cout << ans;

	return 0;
}