[ 백준 11722 ] 가장 긴 감소하는 부분 수열 (C++)

백준의 가장 긴 감소하는 부분 수열(11722) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

주어진 배열에서 일부를 떼어내온 부분 수열 중, 가장 긴 감소하는 부분 수열의 길이를 구해야 하는 문제이다.

이 문제를 풀기 전에, 정말 비슷한 방법으로 해결하고 그에 대한 풀이를 적어놓은 글이 있으니, 아래의 링크에 걸려있는

문제를 먼저 풀어보고, 그 문제의 풀이까지 모두 보고오는 것을 권장한다.

[ 백준 - 가장 긴 증가하는 부분 수열(11053) 문제 바로가기 ]

[ 백준 - 가장 긴 증가하는 부분 수열(11053) 풀이 바로가기 ]

( 지금부터 보실 내용은, 위에 걸어놓은 문제에 대한 풀이글과 굉장히 많은 비교가 들어갑니다 ! )

위의 문제와 굉장히 비슷한 문제이다. 사실 똑같다고 봐도 무방한 문제이다.

이 문제는 위에서 설명한 문제와는 다르게, 가장 긴 '감소하는 부분 수열'을 찾고, 그 길이를 출력해야 하는 문제이다.

증가하는 부분수열을 구하는 방법에 대해서 다시한번 간단하게만 이야기를 해보자면

1. 현재 Index보다 더 작은 Index들을 탐색을 한다.

2. 1의 과정에서 탐색되는 데이터들 중, 현재 값보다 더 작은 값을 가진 데이터들에 대해서 연산을 진행한다.

3. 2의 과정에서 연산은 해당 데이터가 가진 '증가하는 부분 수열의 길이'에 + 1 을 한다.

4. 2 ~ 3의 과정을 반복하면서, 현재 Index가 가질 수 있는 가장 긴 증가하는 부분 수열의 길이를 구한다.

간단하게 말해서 위와 같은 방법으로 구했다.

이 문제는 반대로 감소하는 부분 수열이다.

그럼, 감소하는 부분수열이라는 것은, 정방향으로 봤을 때는 감소하는 부분 수열이지만, 역방향으로 본다면 증가하는 부분 수열이 된다. 예를 들어서 [ 3 , 2 , 1 ] 이라는 수열을 한번 보자.

위의 수열은 "감소하는 수열"이다. 그런데, 역방향으로, 즉 가장 마지막 Index부터 본다면, [ 1 , 2 , 3 ] 으로 증가하는 부분수열이 된다.

즉 ! 이 문제가 위에서 언급한 "가장 긴 증가하는 부분 수열"과 똑같다고 봐도 무방하다고 했던 이유는 "주어진 배열을, 정방향이 아닌, 역방향으로 탐색하면서 가장 긴 증가하는 부분 수열을 찾으면 되는 것" 이기 때문이다.

역방향으로 탐색하기 위해서는 ?? 정말 간단하게, 1번 Index부터 N번 Index까지 순차적으로 탐색을 하던 것을, N번 Index부터 1번 Index로 탐색을 진행해 주면 된다.

중간중간, 감소하는 부분 수열의 길이를 구하는 과정은 역시나 증가하는 부분수열의 길이를 구할 때와 똑같다.

[ 소스코드 ]

#include <iostream>
 
#define endl "\n"
#define MAX 1010
using namespace std;
 
int N, Answer;
int Arr[MAX];
int DP[MAX];
 
int Max(int A, int B) { if (A > B) return A; return B; }
    
void Input()
{
    cin >> N;
    for (int i = 1; i <= N; i++) cin >> Arr[i];
}
 
void Solution()
{
    for (int i = N; i >= 1; i--)
    {
        DP[i] = 1;
        for (int j = N; j > i; j--)
        {
            if (Arr[i] > Arr[j])
            {
                DP[i] = Max(DP[i], DP[j] + 1);
            }
        }
        Answer = Max(Answer, DP[i]);
    }
    cout << Answer << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}