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

문제는 다음과 같습니다.

가장 긴 증가하는 부분 수열 문제와 동일한데, 차이점은 이 수열이 무엇인지까지 저장해야한다는 것입니다.

제가 가장 먼저 풀었던 풀이 방법은 다음과 같습니다.

이 전에는 i까지의 최대 증가 부분 수열의 길이를 벡터에 저장했더라면,
이번에는 벡터 배열을 선언해서,
i까지의 최대 증가 부분 수열을 저장해놓았습니다.

그리고 이중 for문을 돌면서,
길이가 더 최대인 부분수열이 나왔을 경우, 해당 벡터를 갱신하여 더 긴 부분수열을 구하도록 하였습니다.

풀이1: i까지의 최대 증가 부분 수열을 벡터 배열에 저장해놓기

시간복잡도는 O(n^2)일 것이구요,
코드는 다음과 같습니다.

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    vector<int> v[1001]; vector<int> a;
    int n, tmp, j, max_size;
    cin>>n;

    for(int i=0; i<n; i++){
      cin>>tmp;
      a.push_back(tmp);
      max_size=1;
      for(int j=i-1; j>=0; j--){
        if(a[j]<tmp && max_size<v[j].size()+1){
          v[i].clear();
          v[i] = v[j];
          max_size = v[j].size()+1;
        }
      }
      v[i].push_back(tmp);
    }

    int max_idx=0;
    for(int i=1; i<n; i++){
      if(v[i].size() > v[max_idx].size()) max_idx=i;
    }
    cout<<v[max_idx].size()<<endl;
    for(int i=0; i<v[max_idx].size(); i++){
      cout<<v[max_idx][i]<<" ";
    }

    return 0;
}

두번째로 생각한 풀이는 다음과 같습니다.
최대 부분 증가 수열의 최대길이 그리고 바로 이때의 바로 이전 수열의 항의 인덱스 값을 저장하는 것입니다.

풀이2: 이전 수열의 항의 인덱스 값을 저장해두기

그래서 배열 cnt에는 최대 부분 증가 수열의 길이를 담았고,
배열 idx에는 이 최대수열에서 이전 항의 인덱스 값을 저장하였습니다.

그러면 마지막에 가서 다음과 같은 while문을 돌려

    while(max_idx>0){
      res.push_back(a[max_idx]);
      max_idx = idx[max_idx];
      if(max_idx==0) break;
    }

재귀적인 느낌으로 수열의 항들을 거꾸로 찾아갈 수 있습니다.

전체 코드는 다음과 같습니다.

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    vector<int> res;
    int n, tmp, j, max_size;
    int a[1001]={0, };
    int cnt[1001]={0, };
    int idx[1001]={0, };
    cin>>n;

    for(int i=1; i<=n; i++){
      cin>>tmp;
      a[i]=tmp;
      idx[i]=0;
      cnt[i]=1;
      max_size=1;
      for(int j=i-1; j>=1; j--){
        if(a[j]<tmp && max_size<cnt[j]+1){
          idx[i]=j;
          max_size = cnt[j]+1;
          cnt[i]=cnt[j]+1;
        }
      }
    }

    int max_idx=1;
    for(int i=2; i<=n; i++){
      if(cnt[max_idx] < cnt[i]) max_idx=i;
    }
    cout<<cnt[max_idx]<<endl;

    while(max_idx>0){
      res.push_back(a[max_idx]);
      max_idx = idx[max_idx];
      if(max_idx==0) break;
    }

    for(int i=res.size()-1; i>=0; i--) cout<<res[i]<<" ";
    return 0;
}

---

2월 8일 화요일 복습)

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int a[1001]={0, }; int dp[1001]={0, };
    int idx[1001]; fill_n(idx, 1000, -1); // idx: 이전의 인덱스 저장
    int tmp, len, res=1, n, max_idx=0; cin>>n;
    
    for(int i=0; i<n; i++){
      cin>>tmp; a[i]=tmp; len=1;
      for(int j=i-1; j>=0; j--){
        if(a[j]<a[i] && dp[j]+1>len){
          len=dp[j]+1;
          idx[i]=j;
        }
      }
      dp[i]=len;

      if(dp[i]>res){
        res=dp[i]; // 가장 긴 길이 갱신
        max_idx=i; // 길이가 가장 큰 인덱스 갱신
      }
    }

    cout<<res<<"\n";
    
    vector<int> v;
    do{
      v.push_back(a[max_idx]);
      max_idx=idx[max_idx];
    }while(max_idx!=-1);

    sort(v.begin(), v.end());
    for(int i=0; i<v.size(); i++) cout<<v[i]<<" ";

    return 0;
}