[백준(BOJ)] 14002번 : 가장 긴 증가하는 부분 수열 4 - C++[CPP]

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

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

---

⊙ 문제

⊙ 입력

⊙ 출력

⊙ 예제 입출력

⊙ 알고리즘 분류

• 다이나믹 프로그래밍

 

---

 

⊙ 문제 접근 과정

 

이번에는 LIS의 길이만 출력하는 것이 아닌 LIS 수열도 출력해야 하는 문제였다.

---

 

⊙ 문제 풀이

 

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

using namespace std;

int n,temp,index,len;
int a[1001],dp[1001];
vector<int> arr;

int main() {
    cin >> n;

    for(int i=1;i<=n;i++) {
        cin >> a[i];
        len=0;

        for(int j=1;j<i;j++) {
            if(a[i]>a[j])
                len=max(dp[j],len);
        }
        dp[i]=len+1;

        if(temp<dp[i]) {
            temp = dp[i];
            index = i;
        }
    }

    for(int i=index;i>=1;i--) {
        if(temp==dp[i]) {
            arr.push_back(a[i]);
            temp--;
        }
    }

    int size=arr.size();
    cout <<size<<"\n";

    for(int i=0;i<size;i++) {
        cout << arr.back()<<" ";
        arr.pop_back();
    }
}

---

⊙ 결과

 

---

⊙ 마무리

 

 

NONE

 

좋아요는 로그인하지 않아도 누를 수 있습니다!