[백준 C++] 11053 가장 긴 증가하는 부분 수열 - 다이나믹프로그래밍

11053번: 가장 긴 증가하는 부분 수열

#include <iostream>
using namespace std;

int Sequence[1000];
int Length[1000];

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

	int MaxLength = 0;

	int N;
	cin >> N;
	for (int i = 0; i < N; ++i)
	{
		cin >> Sequence[i];

		for (int j = 0; j < i; ++j)
		{
			if (Sequence[j] < Sequence[i]
				&& Length[j] > Length[i])
			{
				Length[i] = Length[j];
			}
		}

		Length[i] += 1;
		if (Length[i] > MaxLength)
		{
			MaxLength = Length[i];
		}
	}

	cout << MaxLength;
}

---

 

수열의 처음 원소부터 마지막 원소까지 DP 배열을 채워주면서 푸는 문제입니다.

 

모든 원소를 순차 탐색하면서 현재 원소 이전 원소 중에 현재 원소보다 값이 작은 원소가 존재하면

해당 원소의 DP 값과 현재 원소의 DP 값을 비교해서 더 큰 값을 넣어주고 +1을 해줍니다.

 

DP 배열을 모두 채우고 나면 최대값을 출력합니다.