[Algorithm]Baekjoon 14002번 :: 가장 긴 증가하는 부분 수열 4

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

14002번: 가장 긴 증가하는 부분 수열 4

 
 
using namespace std;
 
int n;
int arr[1001] = { 0 };
int dp[1001] = { 0 };
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> n;
    
    for (int i = 1; i <= n; ++i)
    {
        cin >> arr[i];
    }
 
    int maxLength = 0;
    int maxIndex = 0;
 
    for (int i = 1; i <= n; ++i)
    {
        for (int j = i - 1; j >= 0; --j)
        {
            if (arr[j] < arr[i])
            {
                dp[i] = max(dp[i], dp[j] + 1);
 
                if (dp[i] > maxLength)
                {
                    maxLength = dp[i];
                    maxIndex = i;
                }
            }
        }
    }
 
    vector<int> answers = { arr[maxIndex] };
    int sNum = dp[maxIndex];
 
    for (int i = maxIndex-1; i >= 1; --i)
    {
        if (dp[i] == sNum - 1)
        {
            answers.push_back(arr[i]);
            --sNum;
        }
    }
 
    cout << maxLength << endl;
 
    for (int i = answers.size() - 1; i >= 0; --i)
    {
        cout << answers[i] << ' ';
    }
}
 
 
 

 

가장 긴 길이뿐만 아니라, 해당하는 수열도 출력해야하는 문제이다.

해본 적 없어서 어떻게해야하지? 하다가, 어제 LCS알고리즘을 배웠던게 떠올라서 응용했더니 통과했다;;

방법은 일단 길이를 구하는과정을 통해 DP테이블을 업데이트 한 후, 최대길이값의 인덱스-1부터 시작해서 점점 인덱스를 낮추면서 기준dp값의 -1씩을 찾아가면 된다.

 

즉, 최대길이가 4였고 마지막인덱스가 6이였다고 가정하면, dp[6] == 4일 것이다.

그러면 5번째 인덱스부터 점점 내려오면서 dp값이 4-1인 3을 먼저 찾는다.

찾으면 해당 인덱스의 숫자를 출력하고 마찬가지로 반복하면 된다.