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

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

시간제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	256 MB	10668	4186	3187	40.301%

문제

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

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

---

예제 입력 1

6
10 20 10 30 20 50

예제 출력 1

4
10 20 30 50

 

 

출처

www.acmicpc.net/problem/14002

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

알고리즘 분류

• 다이나믹 프로그래밍

접근 방법

LIS를 구하는 방법 중 대표적으로 ${O(N^2)}$ 의 방법과 ${O(NlogN)}$의 방법이 있다.

이 문제에서는 N의 범위가 ${{10}^3}$ 이므로 충분히 ${O(N^2)}$의 방법으로 풀 수 있다.

 

다음과 같이 메모이제이션 배열을 선언해보자.

DP[i] = i를 부분 증가 수열의 마지막 원소로 보았을 때, 최장 부분 증가 수열의 길이

그러면, DP[j]가 증가하는 조건은 i < j 인 i에 대해서 max(dp[i]) + 1 이 dp[j] 값이 된다는 것을 알 수 있다.

왜냐하면, 이전까지 구한 최장 부분 증가 수열의 길이 + 1이 결국에는 다음 stage에서도 최장 부분 증가 수열의 길이가 되기 떄문이다.

최종적으로 DP[k] ( 0 <= k < N ) 의 최댓값이 증가 수열의 최장 길이가 된다는 것을 알 수 있다.

 

두번째로 우리가 구해야하는 것은, 가장 긴 부분 수열을 출력하는 것인데 이것은 backtrace라는 배열을 만들어서 메모이제이션 배열이 변화할 때 어떠한 경로를 거쳐서 왔는지 기록하는 것으로 구현이 가능하다.

backtrace배열이 변화하는 경우는 메모이제이션 배열의 값이 변경될 때이다. 

이전에 찾았던 (최장 부분 증가 수열 + 현재 숫자) 가 현재 backtrace배열의 값이 된다.

 

이러한 방식으로 모든 0 <= i < N 인 i에 대하여 backtrace 와 dp 를 초기화 시켜 준다면 여기서 dp[k]가 최댓값이 되는 k에 대해서 dp[k]와 backtrace[k]를 출력하면 우리가 원하는 "가장 긴 증가하는 부분 수열의 길이" 와 "가능한 경로 중 하나"를 출력할 수 있다.

 

소스 코드

#include <bits/stdc++.h>
using namespace std;
int main(void){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int N;
    cin >> N;

    vector<int> arr(N);
    for(int i=0; i<N; i++){
        cin >> arr[i];
    }

    // dp[i] : i까지 검사했을 때 부분 증가 수열의 길이
    vector<int> dp(N, 1);
    // 현재까지 밟고 온 것들의 경로
    vector<int> backtrace[N];
    for(int i=0; i<N; i++){
        backtrace[i].push_back(arr[i]);
    }

    for(int i=1; i<N; i++){
        for(int j=0; j<i; j++){
            if( arr[j] < arr[i] && dp[i] < dp[j] + 1 ){
                dp[i] = dp[j] + 1;
                backtrace[i] = backtrace[j];
                backtrace[i].push_back(arr[i]);
            }
        }
    }
    // dp[0 ~ N-1] 중 가장 큰 값이 가장 긴 증가하는 부분 수열의 길이가 됨
    int max_idx = 0;
    for(int i=1; i<N; i++){
        if( dp[max_idx] < dp[i] ){
            max_idx = i;
        }
    }
    cout << dp[max_idx] << '\n';
    for(auto elem : backtrace[max_idx])
        cout << elem << ' ';
    return 0;
}