[C++] 백준 11053 가장 긴 증가하는 부분 수열

#include <iostream>
 
int arr[1001] = {};
int DP[1001] = {};
 
int main() 
{
	int N = 0;
	std::cin >> N;
 
	for (int i = 0; i < N; ++i)
	{
		std::cin >> arr[i];
	}
 
	int iMax = 0;
 
	for (int i = 0; i < N; ++i)
	{
		DP[i] = 1;
 
		for (int j = 0; j < i; ++j)
		{
			if (arr[i] > arr[j])
			{
				DP[i] = std::max(DP[i], DP[j] + 1);
			}
		}
 
		iMax = std::max(iMax, DP[i]);
	}
 
	std::cout << iMax;
 
	return 0;
}

 

여기서 가장 중요한 것은... 수열이 꼭 등차수열만을 얘기하는 게 아니라는 겁니다.

전 항상 수열을 생각하면 등차수열이라고 생각해서 어떻게 했을까... 했는데...

그냥 단지 수가 이어지는 것, 또한 수열이라 부르는 것입니다.

그렇기 때문에 가장 긴 증가하는 수열은 수가 증가만 하면 됩니다.