[BOJ] 11053 가장 긴 증가하는 부분 수열 / C++

문제

코드

#include <iostream>
#include <vector>
using namespace std;
int v[1001];
int d[1001];
int main()
{
    int n;
    cin>>n;
    for (int i=0;i< n ; i++)
    {
        int in;
        cin>>in;
        v[i]=in;
    }
    for(int i=0;i<n;i++)
    {  
        d[i]=1;
        for(int j=0;j<i;j++)
        {
            if(v[j]<v[i] && d[j]+1 > d[i])
            {
                d[i]=d[j]+1;
            }
        }
    }
    int max=0;
    for(int i=0;i<n;i++)
    {
        if(max<d[i])
            max=d[i];
    }
    cout<<max;
    return 0;
}

풀이

각 숫자마다 순열의 길이를 d[i] 저장해주고, d[i]는 그 i번째 숫자가 앞에숫자보다 크고, 순열의 길이가 가장긴 값에 +1 을 해서 더해주었다

좋은 웹페이지 즐겨찾기