[👊DP뿌시기 #7-3] (BOJ 14002) 가장 긴 증가하는 부분 수열 4

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

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

문제

수열 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의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

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

 

---

접근법

 

https://parvegoongame.tistory.com/65

[👊DP뿌시기 #7] (BOJ 11053) 가장 긴 증가하는 부분 수열

기존의 가장 긴 증가하는 부분 수열 문제에서 부분수열을 출력하는 문제이다.

먼저, vector<int> v[i] 를 만들었다.

의미는 i번째 까지의 가장 긴 증가하는 부분 수열들을 저장하는 벡터로 설정했다.

 

이제 수열을 어떻게 저장할 것인가?

 

크게 두 가지 경우로 나뉜다.

 

1. 조건을 만족하는 경우
2. 조건을 만족하지 않는 경우
(조건: arr[j] < arr[i] )

 

먼저 조건을 만족하는 경우, v[j]를 똑같이 복사한 다음 arr[i]를 추가하면된다.

 

만약 조건을 만족하지 않는 경우에는 arr[i]를 추가하지 않아도 되지 않나?

그렇지 않다.

10
5 9 8 7 6 1 2 3 4 5

만약 위와 같은 예시의 경우, 답은 1 2 3 4 5 이지만

1이 포함되지 않는다.

조건을 만족하지 않지만 수열의 첫번째로 올수도 있기 때문이다.

 

만약 이대로 코딩을 하면 오류가 난다.

중복되는 것들이 추가되기 때문에 vector 대신 set을 이용해서 중복을 제거하자.

 

코드

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

using namespace std;
#define MAX 1001
set<int> v[MAX];
int dp[MAX];
int arr[MAX];


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> arr[i];
    }

    dp[1] = 1;
    v[1].insert(arr[1]);
    for (int i = 2; i <= n; i++) {
        dp[i] = 1;
        for (int j = 1; j < i; j++) {
            // 조건에 부합하면
            if (arr[j] < arr[i]) {
                // 수열이 바뀔 경우
                // 이전꺼에 원래 원소 추가
                if (dp[j] + 1 > dp[i]) {
                    dp[i] = dp[j] + 1, dp[i];
                    v[i] = v[j];
                }
                v[i].insert(arr[i]);
            }
            // 조건에 부적합
            // 첫번째 인덱스로 사용될 수 있기 때문에 저장.
            else
                v[i].insert(arr[i]);
               
        }
    }

    int res = 0;
    int num = 0;
    for (int i = 1; i <= n; i++) {
        if (res < dp[i]) {
            res = dp[i];
            num = i;
        }
    }

    cout << res << "\n";
    for (auto i = v[num].begin(); i != v[num].end(); i++)
        cout << *i << ' ';

    return 0;
}