(14002) 가장 긴 증가하는 부분 수열 4

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

단계별로 풀어보기

32단계(동적 계획법과 최단거리 역추적) 2번째

 

 

 

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

int main() 
{
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int n;
  
  cin >> n;
  
  vector<int> v(n+1), dp(n+1, 1), from(n+1);
  
  for(int i=1;i<=n;i++)  cin >> v[i];
  
  for(int i=2;i<=n;i++){
    for(int j=1;j<i;j++){
      if(v[j]<v[i] && dp[i]<dp[j]+1){
        dp[i]= dp[j]+1;
        from[i]= j;
      }
    }
  }
  
  int maxidx= 1;
  vector<int> res;
  
  for(int i=1;i<=n;i++){
    if(dp[maxidx]<dp[i])  maxidx= i;
  }
  
  cout << dp[maxidx] << "\n";
  
  while(maxidx){
    res.push_back(v[maxidx]);
    
    maxidx= from[maxidx];
  }
  
  for(int i=res.size()-1;i>=0;i--)  cout << res[i] << " ";
  
  return 0;
}