백준 14002 가장 긴 증가하는 부분 수열 4

가장 긴 증가하는 부분 수열 문제를 그대로 적용한 후, 더 증가하는 인덱스를 참조할 때마다 해당하는 인덱스에 

이전의 수열 저장값을 저장하고 뒤에 새로 추가될 값을 추가해 주었다. (뭔 소리지?)

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <algorithm>

using namespace std;
vector<int> lst[1002];

int main()
{
  int n;
  int arr[1002];
  int dp[1002];
  int max_val = -1;
  int max_idx= -1;
  cin>>n;
  for (int i = 0; i < n; i++)
    cin>>arr[i];
  
  for (int i = 0; i < n; i++)
  {
    dp[i] = 1;
    lst[i].push_back(arr[i]);
    for (int j = 0; j < i; j++)
    {
      if(arr[i] > arr[j])
      {
        if(dp[i] > dp[j] + 1)
          dp[i] = dp[i];
        
        else
        {
          dp[i] = dp[j]+1;        
          //lst[i].clear();
          lst[i] = lst[j];
          lst[i].push_back(arr[i]);
        }
      }
    }
    max_val = max(max_val, dp[i]);
    if(max_val == dp[i])
      max_idx = i;
  }

  cout<<max_val<<"\n";
  for (int i  =0 ; i < lst[max_idx].size(); i++)
  {
    cout<<lst[max_idx][i] << " ";
  }cout<<"\n";
  return 0;
}

코드를 보면 이해가 쉬운데, dp 값을 비교해 주면서 dp[j] 에 값을 추가하는 것이 더 긴 수열을 만드는 방법일 때를 주목해보자.

32 ~ 36을 보면, dp 를 갱신한 후, i 번째 lst dp 에 j 번째 dp 값을 옮긴 후 arr[i] 값을 뒤에 붙여주는 것을 볼 수 있다.

clear 로 리스트를 새로 비워주어야 하나 싶었지만 없어도 상관 없다!!