백준 11053 - 가장 긴 증가하는 부분 수열

문제 설명

 

 

=> DP 문제이다. 

=> 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 문제이다. 

=> 수열 A =[10, 20, 10, 30, 20 ,50]

=> 가장 긴 증가하는 부분 수열 A = [10, 20, 30, 50]

 

 

=> D[N] : A[i] 를 마지막으로 하는 가장 긴 증가하는 부분 수열의 길이

=> D[i]는 A[i]를 반드시 포함하여야 한다. 

 

 

 

 

 

=> 위의 그림을 보면 어떤 방식으로 이루어지는지 알 수 있다. 

 

 

 

 

 

 

 

 

**가장 긴 증가하는 부분 수열 구하는 알고리즘 

 for(int i=0; i<N; i++)
    {
        D[i]=1;
        for(int j=0; j<i; j++)
        {
            if(A[j] < A[i] && D[i] < D[j]+1)
            {
                D[i] = D[j]+1;
            }
        }
    }

 

 

 

 

 

 

 

 

 

 

<전체코드>

#include <iostream>
#include <algorithm>
#include <string>



using namespace std;




int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    int A[1001];
    
    int N;
    cin >> N;
    
    
    for(int i=0; i<N; i++)
    {
        cin >> A[i];
    }
    
    int D[N];
    
    for(int i=0; i<N; i++)
    {
        D[i]=1;
        for(int j=0; j<i; j++)
        {
            if(A[j] < A[i] && D[i] < D[j]+1)
            {
                D[i] = D[j]+1;
            }
        }
    }
        
    cout << *max_element( D, (D+N) );
    
}

 

 

 

 

실행 예 

실행 예 2