[Algorithm] Baekjoon 11053번 : 가장 긴 증가하는 부분수열

https://www.acmicpc.net/problem/11053

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

vector<int> v;
int dp[1001];
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    int n = 0;
    int input = 0;
    int result = 0;
    cin >> n;
 
    for (int i = 0; i < n; i++)
    {
        cin >> input;
        v.push_back(input);
    }
 
    for (int i = 0; i < v.size(); i++)
    {
        dp[i] = 1;
        int maxNum = 0;
 
        for (int j = 0; j < i; j++)
        {
            if (v[i] > v[j])
            {
                maxNum = max(maxNum, dp[j]);
            }
        }
 
        dp[i] += maxNum;
        result = max(dp[i], result);
    }
 
    cout << result << endl;
}

DP문제다.

주어진 수열에 대해 증가하는 부분수열의 최대길이를 구하는 문제이다.

문제 예시를 그대로 들고오면,

 

수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

 

주어진 수열 그대로에서 증가하는 부분 수열 중 가장 긴 부분수열의 길이를 구하면 된다.

원소가 아니라 인덱스가 DP랑 매핑이 된다고 생각해야 한다.

즉, DP[0]은 수열[0]의 최대 길이값이다. 

해당 인덱스 이전의 원소값이 자기자신보다 작은게 있어야만 +1씩 된다.

 

그렇기 때문에 수열을 반복문 돌면서 이전인덱스들까지 반복문을 돌린다.

기준으로 잡은 수열의 원소값보다 작은 인덱스들을 찾고, 그 인덱스들 중 가장 dp값이 큰 값을 찾아서 더해주면 된다.