[백준] 11722 : 가장 긴 감소하는 부분 수열

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

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

---

• 가장 ~ 증가하는 부분 수열 시리즈와 비슷한 내용인데, 수열의 방향만 달라진 문제이다.
• 11053 번 문제와 11055 번 문제를 둘 다 풀었기 때문에 쉽게 접근할 수 있었다.
• i번째 값에 해당 위치까지 가장 긴 최소 부분 수열의 길이를 담아주는 DP 배열을 사용한다.
• https://bconfiden2.tistory.com/161

---

#include <iostream>
#include <vector>

using namespace std;

int main(void)
{
    int N;
    cin >> N;

    vector<int> v(N, 0);                // 실제 데이터
    vector<int> answer(N, 0);           // 각 위치별로 가장 긴 감소하는 부분 수열의 길이

    for(int i = 0 ; i < N ; i++)
    {
        cin >> v[i];
    }

    int maxi = 0;
    for(int i = 0 ; i < N ; i++)
    {
        int temp = 1;                   // i 번째 위치의 가장 긴 길이를 담을 값
        for(int j = 0 ; j < i ; j++)    // 자신 이전까지 모든 최대 길이들을 확인
        {
            if(answer[i] < answer[j] + 1 && v[i] < v[j])    // 최대 길이가 갱신될 경우(감소 부분 수열 조건도 만족)
            {
                answer[i] = answer[j] + 1;
                temp = answer[i];
            }
        }
        if(temp > maxi) maxi = temp;    // 이번 값이 전체값들 중 최대길이인지 확인
        answer[i] = temp;               // i 번째 값 업데이트
    }
    cout << maxi << endl;
}