11722번

11722번 - 가장 긴 감소하는 부분 수열

D[N]을 N번째 자리 수를 포함하는 가장 긴 감소하는 부분 수열의 길이

로 점화식을 세웠다.

11053,11055 번과 아주 유사한 문제.

앞의 문제들은 완전 탐색 코드를 아래와 같은 방식으로 안 풀었지만 이건 이렇게 풀어봄.

<완전 탐색 코드 - 시간 초과>

#include<iostream>
#include<algorithm>
using namespace std;
 
int A[1001];
int ans;
void go(int n,int len)
{
    ans = max(len, ans);
 
    for (int i = 1; i < n; i++)
    {
        if (A[i] > A[n])
        {
            go(i, len + 1);
        }
    }
 
    return;
 
}
int main()
{
    int N;
    cin >> N;
 
    for (int i = 1; i <= N; i++)
    {
        cin >> A[i];
    }
 
    for (int i = 1; i <= N; i++)
    {
        go(i,1);
    }
 
    cout << ans << endl;
    return 0;
}

<정답 코드 - DP >

#include<iostream>
#include<algorithm>
using namespace std;
 
int A[1001];
int D[1001];
int ans;
int go(int n)
{
    if (D[n] != 1)
    {
        return D[n];
    }
 
    for (int i = 1; i < n; i++)
    {
        if (A[i] > A[n])
        {
            D[n]=max(D[n],go(i)+1);
        }
    }
 
    return D[n];
 
}
int main()
{
    int N;
    cin >> N;
 
    for (int i = 1; i <= N; i++)
    {
        cin >> A[i];
        D[i] = 1;
    }
 
    for (int i = 1; i <= N; i++)
    {
        ans =max(ans,go(i));
    }
 
    cout << ans << endl;
    return 0;
}