11053번

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

★★★★★다시 풀 문제★★★★★

D[N]을 N번째 수를 포함하는 가장 긴 증가하는 부분 수열의 길이 로 정의 했습니다.

그렇기 때문에 N번째 수를 무조건 포함하고 1 ~ N-1 번째 수 각각에 대해서 for문을 돌렸습니다.

점화식 조건에 의해 D[N]은 최소 1이 되기 때문에 그렇게 초기화하였고, 2이상의 값에 대해서 캐시로 간주하고 리턴해주었습니다.

이렇게 하면 왜 안될까? 생각하면서 오래 고민했던 문제...

생각해보니 처음에 작성한 완전탐색 코드부터 문제가 있었던 것 같다. 

D의 값을 해당 범위 초기화하는 것과 전부 초기화 하는데 문제가 발생 -> Q&A에 질문

<완성 코드>

#include<iostream>
#include<algorithm>
#include<string.h>
 
using namespace std;
int A[1001];
int D[1001];
int N;
int ans;
int go(int n)
{
    if (D[n] >=2)
    {
        return D[n];
    }
 
    for (int i = 1; i < n; i++)
    {
        if (A[n] > A[i])
        {
            D[n] = max(D[n],go(i) + 1);
        }
    }
 
    return D[n];
}
 
int main()
{
    cin >> N;
    memset(D, -1, sizeof(D));
    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;
}