<Baekjoon>#14002가장 긴 증가하는 부분 수열4 (Longest increasing subsequence 4) c++
바로 앞에서 풀었던 문제가 부분 수열의 길이만 출력하는 거라면, 이번에는 가장 긴 증가하는 부분수열도 출력해야 한다.
dp의 값이 가장 큰 A의 값부터 시작해서 하나씩 작아지게 역순으로 B에 push_back 한다.
(처음에 dp의 값이 가장 작은 A값부터 B에 push를 했다가 한참을 헤맸다..)
dp[5]=4 A[5]=50의 값을 B에 push
dp[3]=3 A[3]=30의 값을 B에 push
dp[1]=2 A[1]=20의 값을 B에 push
dp[0]=1 A[0]=10의 값을 B에 push
#include<iostream>
#include<vector>
using namespace std;
const int MAX = 1001;
void lis(const vector<int>& A, int n) {
vector<int>B;
int dp[MAX];
dp[0] = 1;
int maxLen = 1;
for (int i = 1; i < n; i++) {
dp[i] = 1;
for (int j = 0; j < i; j++) {
if (A[i] > A[j] && dp[i] < dp[j] + 1)
dp[i] = dp[j] + 1;
maxLen = max(maxLen, dp[i]);
}
}
int k = maxLen;
for (int i = n - 1; i >= 0; i--) {
if (k == 0)
break;
if (dp[i] == k) {
B.push_back(A[i]);
k--;
}
}
cout << maxLen << endl;
while (!B.empty()) {
cout << B.back() << " ";
B.pop_back();
}
}
int main() {
int k;
cin >> k;
vector<int>A(k);
for (int i = 0; i < k; i++)
cin >> A[i];
lis(A, k);
return 0;
}
Author And Source
이 문제에 관하여(<Baekjoon>#14002가장 긴 증가하는 부분 수열4 (Longest increasing subsequence 4) c++), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@kimmy/Baekjoon14002가장-긴-증가하는-부분-수열4-Longest-increasing-subsequence-4-c저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)