[알고리즘 문제] 백준11722 - 가장 긴 감소하는 부분 수열

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

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

LIS와 반대로 가장 긴 감소하는 부분 수열을 구하는 문제 입니다.

 

LIS의 경우 첫번째 ~ i번째 수를 검사하지만 가장 긴 감소하는 부분 수열은 i ~ 마지막 부분을 검사해야 합니다.

 

2가지 방법으로 풀어봤는데, 첫번째 방법은 배열을 뒤집어 LIS처럼 구하는 방식이고, 두번째 방법은 배열을 안뒤집고 푸는 방법입니다.

 

1. 배열 reverse

#include <iostream>
#include <algorithm>

using namespace std;

int arr[1001] = {0};
int dp[1001] = {0};

int main()
{
    int n;
    int result = 0;

    cin >> n;

    int arr1[1001] = {0};
    int arr[1001] = {0};
    int dp[1001] = {0};

    for (int i = 1; i <= n; i++)
    {
        cin >> arr1[i];
    }

    for (int i = n; i >= 1; i--)
    {
        arr[n - i + 1] = arr1[i];
    }

    for (int i = 1; i <= n; i++)
    {
        int cnt = 0;
        dp[i] = 1;
        for (int j = 1; j < i; j++)
        {
            if (arr[i] > arr[j])
            {
                cnt = max(cnt, dp[j]);
            }
        }
        dp[i] += cnt;
        result = max(result, dp[i]);
    }

    cout << result;
    return 0;
}

 

2. 그냥 풀기

#include <iostream>
#include <algorithm>

using namespace std;

int arr[1001] = {0};
int dp[1001] = {0};

int main()
{
    int n;
    int result = 0;

    cin >> n;

    int arr1[1001] = {0};
    int arr[1001] = {0};
    int dp[1001] = {0};

    for (int i = 1; i <= n; i++)
    {

        cin >> arr[i];
    }

    for (int i = n; i >= 1; i--)
    {
        int cnt = 0;
        dp[i] = 1;
        for (int j = i; j <= n; j++)
        {
            if (arr[i] > arr[j])
            {
                cnt = max(cnt, dp[j]);
            }
        }
        dp[i] += cnt;
        result = max(result, dp[i]);
    }
    
    cout << result;
    return 0;
}