[백준/중하] 11053번 가장 긴 증가하는 부분 수열 (LIS,DP,다이나믹 프로그래밍)

이 문제는 LIS(Longest increasing subsequence) 기본 문제이다

문제를 푸는 방법은 현재 인덱스를 검사할때 그 전에 인덱스를 하나하나 살펴보면서 현재 인덱스에 있는 숫자 보다 작은 것의 인덱스 중에

가장 큰 dp값(가장 긴 부분증가수열)을 택하고 그것에 1을 더하면 현재 인덱스에서 가장 긴 부분 증가 수열을 구하게 된다.

예를 하나 들면

10 20 10 30 20 50 이 있을때

30에서 가장 긴 부분 증가수열을 구하려면(dp[3]에 들어가는 값)

30과 10 20 10 을 차례대로 비교를 해 나간다 그중에 10,20,10모두 30보다 작으므로 후보가 될 수 있다.

이 세 숫자 중에서 dp[0],dp[1],dp[2]에 저장된 값중에 가장 큰 것에 1을 더해주게되면 30에서의 가장긴 부분 증가 수열이다.

dp에 저장된 값은 현재 인덱스에서의 가장 긴 부분 증가 수열의 길이이다.

이런 식으로 문제를 풀면 된다.

전체 코드

#include <iostream>
 
using namespace std;
int input[1001];
int dp[1001];
int main()
{
    int n;
    cin>>n;
    for(int i=0; i<n; i++)
        cin>>input[i];
    
    dp[0] = 1;
    for(int i=0; i<n; i++)
    {
        int maxx = 0;
        for(int j=i-1; j>=0; j--)
        {
            if(input[i]>input[j])
            {
                maxx = max(maxx,dp[j]);
            }
        }
        dp[i] = maxx+1;
    }
    int ret = -1;
    for(int i=0; i<n; i++)
        ret = max(dp[i],ret);
    
    cout<<ret<<endl;
    
    
    return 0;
}