Boj 11053 c++ 가장 긴 증가하는 부분수열

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

 

 

LIS의 전형적인 문제로, dp문제이다. 많은 곳에 활용되는 알고리즘이기에 알아두면 좋다. 모든 부분에 대하여 가장 긴 증가하는 부분수열의 최솟값은 1이다. 이후에는 특정 인덱스에 대하여 그것보다 작은 값이 있으면 그 자리의 dp배열 값에 1을 더한 값과 현재 배열 값 중 더 큰 값으로 초기화한다. 이는 이전의 가장 긴 부분 수열의 길이를 기억하면 유리하다는 논리하에 풀이한 것이다.

 

이때 dp배열의 정의는 i번째 원소를 끝으로 하는 가장 긴 증가하는 부분수열의 길이이다.

j번째 원소를 만났을 때 max로 보정해주는 이유는 참조하는 j번째 원소의 LIS길이에 따라 값이 달라질 수 있기에 그 중 최댓값만을 취하기 위해서이다.

#include<iostream>
using namespace std;
int arr[1010];
int dp[1010];//가장 긴 증가하는 부분 수열의 길이
int main(){
    int N, ans=0;
    cin>>N;
    for(int i=1; i<=N; i++){
        cin>>arr[i];
    }
    for(int i=1; i<=N; i++){
        dp[i]=1;//가장 긴 증가하는 부분 수열의 길이는 항상 최소 1
        for(int j=i-1; j>=1; j--){
            if(arr[i]>arr[j]){
                dp[i]=max(dp[i], dp[j]+1);
            }
        }
        ans=max(ans, dp[i]);
    }cout<<ans; 
}