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

 

 

문제

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)

 

출력

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

둘째 줄에는 가장 긴 증가하는 부분 수열을 출력한다. 그러한 수열이 여러가지인 경우 아무거나 출력한다.

 

접근 방식

 

가장 유명한 DP 문제인 가장 긴 증가하는 부분 수열의 변형 문제이다

수열의 길이 자체는 DP로 간단하게 풀 수 있다

for 반복문을 i를 1 ~ N번 돌면서

이중 반복문으로 j를 i-1 ~ 1 을 확인하면서

arr[i]가 arr[j]보다 클 시 dp[i]를 dp[i], dp[j]+1 중에 큰 값으로 정해주면 된다.

이때, 부분 수열 자체를 구하는 것은

이미 정해둔 dp값중에 가장 큰 값을 가져와서

큰값부터 해당하는 인덱스를 배열에서 가져오면 된다!

 

처음에는 dp 돌면서 부분 수열을 같이 구해주려고 했는데 

그렇게 하니까 모든 배열이 담겼다 ;;

 

코드

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

int N;
int arr[1002], dp[1001];
vector<int> ans;

int main() {
    cin>>N;
    for(int i=1; i<=N; i++) cin>>arr[i];

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

    int max_len = *max_element(dp+1, dp+N+1);
    cout<<max_len<<'\n';
    
    for(int i=N; i>=1; i--) {
        if(dp[i] == max_len) {
            ans.push_back(arr[i]);
            max_len--;
        } 

    }

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