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

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

 

문제

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

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

 

 

풀이

11053번 가장 긴 증가하는 부분 수열 문제의 확장 버전이다. LIS의 길이뿐 아니라 LIS를 이루는 수열을 구하는 문제다.

[11053 가장 긴 증가하는 부분 수열 문제] | [11053 가장 긴 증가하는 부분 수열 풀이]

 

LIS의 길이를 구하는 데까지는 위 문제와 같다. 문제를 풀기 위해 위 문제의 풀이에서 prev 배열을 만들어 LIS의 길이가 증가한 경우에 대해서만 이전 수의 index를 저장한다. 그리고 차례대로 역추적하면서 해당 index의 수를 배열에 담는다. 배열에 담긴 수를 뒤부터 차례대로 출력한다.

 

 

코드

#include <bits/stdc++.h>
using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  int n;
  cin >> n;
  vector<int> v(n), dp(n, 1), prev(n, -1);
  for (int i = 0; i < n; i++)
    cin >> v[i];
  for (int i = 0; i < n; i++)
    for (int j = 0; j < i; j++)
      if (v[i] > v[j]) {
        if (dp[i] < dp[j] + 1)
          prev[i] = j;
        dp[i] = max(dp[i], dp[j] + 1);
      }
  int idx = 0, m = 0;
  for (int i = 0; i < n; i++)
    if (dp[i] > m) {
      m = dp[i];
      idx = i;
    }
  cout << m << '\n';
  int tmp = idx;
  vector<int> ans;
  while (tmp >= 0) {
    ans.push_back(v[tmp]);
    tmp = prev[tmp];
  }
  for (int i = ans.size() - 1; i >= 0; i--)
    cout << ans[i] << ' ';
  cout << '\n';
  return 0;
}