[ 백준 14002 ] 가장 긴 증가하는 부분수열4 (C++)

백준의 가장 긴 증가하는 부분수열4(14002) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

먼저, 문제를 풀기 전에 아래에 있는 문제를 풀고 풀이까지 보고 오는 것을 권장한다.

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

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

위의 문제와 이 문제의 차이점은, 위의 문제는 단순히 가장 긴 증가하는 부분수열의 길이를 구하면 되는 문제였지만, 지금 이 문제는 가장 긴 증가하는 부분 수열의 길이와 해당 수열까지 출력을 해야 하는 문제이다.

먼저, 가장 긴 증가하는 부분수열에 대한 전체적인 로직은 위의 풀이와 동일하다. 따라서 따로 이야기 하지 않겠다.

그럼, 가장 긴 증가하눈 부분 수열을 구하는 과정을 알아보자.

위의 문제에서, 가장 긴 증가하는 부분 수열의 길이를 구하기 위해서 DP[]라는 int형 1차원 배열을 사용해 주었었다.

DP[A] = B의 의미는, "A번째 값이 가지는 가장 긴 증가하는 부분 수열의 길이는 B입니다." 를 의미했었다.

위와 동일한 원리로, 수열을 저장할 수 있는 배열을 하나 더 선언해 주었다.

수열을 저장해야 하기 때문에, 값들이 순차적으로 추가될 수 있어야 하기 때문에, 본인은 vector<int> 형을 자료형으로 가지는 배열을 하나 선언해 주었다.

vector<int> LIS[] 꼴의 형태로 벡터 배열을 만들어 주었는데, LIS[A] = { 벡터에 삽입된 원소들 } 의 의미는

"A번째 값이 가지는 가장 긴 증가하는 부분 수열은 벡터에 삽입된 원소들 입니다." 를 의미한다.

가장 긴 증가하는 부분 수열을 갱신할 수 있을 때는, 기존에 저장되어 있던 값들을 모두 삭제해주고(clear() 함수 사용) 갱신할 수 있는 값을 새로 저장해 주면 된다.

[ 소스코드 ]

#include <iostream>
#include <vector>
 
#define endl "\n"
#define MAX 1010
using namespace std;
 
int N;
int Arr[MAX];
int DP[MAX];
vector<int> LIS[MAX];
vector<int> Answer;
 
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 = 1; i <= N; i++)
    {
        DP[i] = 1;
        LIS[i].push_back(Arr[i]);
        for (int j = 1; j < i; j++)
        {
            if (Arr[i] > Arr[j])
            {
                if (DP[i] < DP[j] + 1)
                {
                    LIS[i].clear();
                    LIS[i] = LIS[j];
                    LIS[i].push_back(Arr[i]);
                    DP[i] = DP[j] + 1;
                }
            }
        }
        if (Answer.size() < LIS[i].size())
        {
            Answer = LIS[i];
        }
    }
 
    cout << Answer.size() << endl;
    for (int i = 0; i < Answer.size(); i++) cout << Answer[i] << " ";
    cout << 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;
}