[백준 11053번] 가장 긴 증가하는 부분 수열 (C++)

아이디어

그림으로 보면 약간 이런느낌으로 풀었다.

v[0]는 당연히 1일거고.

v[1]부터 앞을 탐색해서 자신보다 작은걸 찾아야하고( 증가하는 수열이므로 )

그중에서 dp값이 가장 높은걸 찾아야한다.

( 30을 예로들면 ( 20, dp=2) , (10, dp=1)을 찾을 수 있으니,(10,dp=1)은 무시해야한다는 의미.

2+1이 되야지 1+1이 되면 안되니까.)

 

C++ 풀이

#include <bits/stdc++.h>

using namespace std;
vector<int> v;
int dp[1001];
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int N;
    int result=1;
    cin >> N;
    for(int i = 0 ; i< N; i++)
    {
        int tmp;
        cin >> tmp;
        v.push_back(tmp);
    }

    dp[0] =1;
    for(int i =1; i<N;i++)
    {
        int m =0;
        for(int j = i-1; j>=0 ; j--)
        {
            if(v[i]>v[j]) //현재 v[j]보다 작고
            {
                if(m <dp[j]){ // 가진 dp들중 최대값을 찾아서
                    m = dp[j];
                }
            }
            //if(v[i] > v[j] && m<dp[j]) m = dp[j];
        }
        dp[i] = m+1; //그 최대값의 +1로 갱신한다.
        if(result < dp[i])
            result = dp[i]; //dp배열들의 최대값을 항상 가지고있는다.
    }

    cout << result;
}