🙇‍♀️최대 부분 증가수열 (LIS)

N개의 자연수로 이루어진 수열이 주어졌을 때, 그 중에서 가장 길게 증가하는(작은 수에서 큰 수로) 원소들의 집합을 찾는 프로그램을 작성하라.

예를 들어, 원소가 2, 7, 5, 8, 6, 4, 7, 12, 3 이면 가장 길게 증가하도록 원소들을 차례대로 뽑아내면 2, 5, 6, 7, 12를 뽑아내어 길이가 5인 최대 부분 증가수열을 만들 수 있다.

▣ 입력설명
첫째 줄은 입력되는 데이터의 수 N(1≤N≤1,000, 자연수)를 의미하고, 
둘째 줄은 N개의 입력데이터들이 주어진다. 

▣ 출력설명
첫 번째 줄에 부분증가수열의 최대 길이를 출력한다.

▣ 입력예제 1 
8
5 3 7 8 6 2 9 4

▣ 출력예제 1
4

🚀풀이

이 문제에서 dp는 해당 위치에서의 숫자가 수열의 맨 마지막일 때 최대 부분 증가 수열 값을 나타낸다.

그래서 dp[1] = 1;로 초기화 된다.

2부터 순회를 하는데 j는 i의 앞을 탐색한다.

i위치의 값이 수열의 마지막이므로 i위치 값보다 작을 경우를 탐색하고 그 중 최댓값을 찾아서 +1을 한다.

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include<iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

int dp[1001], arr[1001], n, res = 0;

void solve()
{
	cin >> n;
	for (int i = 1; i <= n; ++i)
	{
		cin >> arr[i];
	}

	dp[1] = 1;

	for (int i = 2; i <= n; ++i)
	{
		int maxNum = 0;
		for (int j = i - 1; j >= 1; --j)
		{
			if (arr[j] < arr[i] && dp[j] > maxNum)
			{
				maxNum = dp[j];
			}
		}

		dp[i] = maxNum + 1;
		res = max(dp[i], res);
	}

	cout << res;
}

int main() 
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	freopen("input.txt", "rt", stdin);

	solve();

	return 0;
}

참고