챕터3-14. DP | 문제 풀이3 - (3) 백준 No.11722 : 가장 긴 감소하는 부분 수열

가장 긴 감소하는 부분 수열 문제

- https://www.acmicpc.net/problem/11722

문제요약

수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열의 길이를 구하는 문제
부분 수열이란?  수열에서 일부를 선택한 수열이다.
ex) A = {10, 30, 10, 20, 20, 10}
      가장 긴 감소하는 부분 수열 A = {10, 30, 10, 20, 20, 10}
      => 길이는 3

해결 방법

* 바로 전전 문제를 조금 수정해서 풀 수 있다.
   방법 1. 입력으로 주어진 수열을 reverse해서 '가장 긴 증가하는 부분 수열의 길이를 구하는 방법'
   방법 2. 왼쪽 -> 오른쪽 순으로 값을 구하는 것이 아닌, 오른쪽 -> 왼쪽 순으로 '가장 긴 증가하는 부분 수열의 길이를 구하는 방법'

<Bottom-up 방식>

(1) 구현
-> 'for문을 이용한 반복문'으로 구현

// 방법1
#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int main()
{
    int n;
    cin >> n;

    vector<int> a(n);
    vector<int> d(n);

    for (int i = 0; i < n; i++)
        cin >> a[i];
    
    // 역순으로 변경
    reverse(a.begin(), a.end());

    // 가장 긴 증가하는 부분 수열의 길이를 구하는 방법 이용
    for (int i = 0; i < n; i++)
    {
        d[i] = 1;

        for (int j = 0; j < i; j++)
        {
            if (a[j] < a[i] && d[i] < d[j]+1)
                d[i] = d[j]+1;
        }
    }

    cout << *max_element(d.begin(), d.end()) << "\n";
}

// 방법2
#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int main()
{
    int n;
    cin >> n;

    vector<int> a(n);
    vector<int> d(n);

    for (int i = 0; i < n; i++)
        cin >> a[i];

    // 역순으로 가장 긴 증가하는 부분 수열의 길이를 구하는 방법 이용
    for (int i = n-1; i >= 0; i--)
    {
        d[i] = 1;

        for (int j = n-1 ; j > i; j--)
        {
            if (a[j] < a[i] && d[i] < d[j]+1)
                d[i] = d[j]+1;
        }
    }

    cout << *max_element(d.begin(), d.end()) << "\n";
}

(2) 시간복잡도
= for 문의 반복 횟수 

이 방법을 사용하면 N개의 칸을 채워야 하고, 한칸 D[i]의 값을 채울 때 A[i]번을 A[1] ~ A[i-1]번과 모두 비교하므로 
시간복잡도는 N * O(N) = O(N^2)이 된다.