[백준 C++] 14002 가장 긴 증가하는 부분 수열 4 - 다이나믹프로그래밍

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

cpp

#include <iostream>
#include <stack>
using namespace std;

int Sequence[1000];
int DP[1000];
stack<int> LIS;

int main()
{
‌ios::sync_with_stdio(false);
‌cin.tie(NULL); cout.tie(NULL);

‌int Max = 0;

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

‌‌for (int j = 0; j < i; ++j)
‌‌{
‌‌‌if (Sequence[j] < Sequence[i]
‌‌‌‌&& DP[j] > DP[i])
‌‌‌{
‌‌‌‌DP[i] = DP[j];
‌‌‌}
‌‌}

‌‌DP[i] += 1;
‌‌if (DP[i] > Max)
‌‌{
‌‌‌Index = i;
‌‌‌Max = DP[i];
‌‌}
‌}

‌LIS.emplace(Sequence[Index]);

‌int j = Index;
‌for (int i = Index - 1; i >= 0; --i)
‌{
‌‌if (DP[i] == DP[j] - 1)
‌‌{
‌‌‌LIS.emplace(Sequence[i]);
‌‌‌j = i;
‌‌}
‌}

‌cout << Max << '\n';
‌while (!LIS.empty())
‌{
‌‌cout << LIS.top() << ' ';
‌‌LIS.pop();
‌}
}

---

 

다이나믹 프로그래밍으로 최장 증가 수열의 길이와 그 원소를 구하는 문제입니다.

풀이 과정은 다음과 같습니다.

 

첫번째 수부터 N번째 수까지 순차 탐색을 통해서 DP배열에 현재 수까지의 최장 증가 수열 길이를 저장해줍니다.

(반복문 내부에서 현재 수까지의 이전 수를 한번 더 순차 탐색합니다. 현재 수보다 작은 수 중 가장 큰 DP 값을 물려받고 +1해준 값을 저장합니다.)

 

그리고 가장 큰 DP 값을 저장한 인덱스를 기억한 다음,

해당 인덱스부터 역으로 추적하면서 스택 자료구조에 수를 담아줍니다.

해당 인덱스 DP 값부터 -1씩 해가면서 DP 값이 일치하는 수를 담아주면 됩니다.