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

11722. 가장 긴 감소하는 부분 수열 / c++ / Silver2 / 13분

문제

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

1. 길이가 N인 수열 A가 주어진다.
2. 감소 부분 수열 중 가장 긴 수열의 길이를 출력

접근 방식

동적 프로그래밍

1. 자기 자신 왼편에서 자기보다 큰 수들 중 dp값이 가장 큰 수 + 1을 현재 dp에 저장한다.

문제 풀이

#pragma GCC optimize("Ofast")
#include <iostream>
using namespace std;
inline int MAX(int A, int B) { return A > B ? A : B; }

int N;
int arr[1'000];
int dp[1'000] = {};
int answer = 0;

int DP(int num)
{
    if (dp[num] == 0)
    {
        int maxNum = 0;
        for (int i = 0; i < num; ++i)
        {
            if (arr[i] > arr[num])
                maxNum = MAX(maxNum, DP(i));
        }
        dp[num] = maxNum + 1;
        answer = MAX(answer, dp[num]);
    }

    return dp[num];
}

int main()
{
    ios::sync_with_stdio(0); cin.tie(0);

    cin >> N;

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

        DP(i);
    }

    cout << answer << '\n';

    return 0;
}

다시 생각해 볼 점

1. ~한 부분 수열 문제는 DP가 많다.