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

문제 링크입니다 https://www.acmicpc.net/problem/14002

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

'11053번 가장 긴 증가하는 부분 수열' 문제(https://seokeeee.tistory.com/61)와 유사한 문제였습니다. 수열 하나가 주어졌을 때, 가장 긴 증가하는 부분 수열의 길이와 그 수열을 출력하는 문제였고, '11053번 문제'와 동일하게 "dp[N] : 크기가 N인 수열에서 가장 긴 증가하는 부분 수열의 길이"라 하였으며 자세한 풀이 방법은 주석 참고해주세요!

 

 

[소스코드]

 

#include<cstring>
#include<cstdio>
using namespace std;
 
//    dp[N] : 크기가 N인 수열에서 가장 긴 증가하는 부분 수열의 길이
// inDex[K] : 크기가 K인 가장 긴 증가하는 부분 수열에서 맨 끝 직전 수의 index
int n, num[1000], dp[1000], inDex[1000], result[1000];
 
int main(void) {
 
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        scanf("%d", &num[i]);
 
    // dp[0]부터 dp[n-1]까지 값을 결정합니다
    for (int i = 0; i < n; i++) {
 
        // 길이가 1인 수열은 모두 증가하는 수열(dp[i] = 1)
        // inDex[i]의 초기값 -1로 설정
        dp[i] = 1, inDex[i] = -1;
 
        // 현재 결정하는 칸보다 왼쪽에 있는 모든 칸에 대해
        for (int j = 0; j < i; j++) {
 
            // 현재 칸에 있는 j번째 칸의 수보다 더 크고, 현재 결정한 값이
            // (j까지의 가장 긴 증가하는 부분 수열의 길이 + 1)보다 작다면
            if (num[j] < num[i] && dp[i] < dp[j] + 1) {
 
                // 현재 결정한 값을 더 긴 값으로 update 해줍니다
                dp[i] = dp[j] + 1;
                // 현재 칸과 j번째까지의 길이를 합친거라는 표시를 해줍니다
                inDex[i] = j;
            }
        }
    }
 
    // dp 배열을 순회하며 최댓값과 그때의 인덱스 값을 찾고
    int ans = 0, idx = 0;
    for (int i = 0; i < n; i++)
        if (ans < dp[i]) {
            ans = dp[i];
            idx = i;
        }
    // 최대 길이를 먼저 출력하고
    printf("%d\n", ans);
    
    // 위에서 구한 idx 값이 음수가 아닌동안 while loop
    int idx2 = 0;
    while (idx >= 0) {
 
        // idx 부터 inDex 배열에 저장해둔 모든 인덱스에 해당하는
        // 수를 result 배열에 저장합니다
        result[idx2++] = num[idx];
        idx = inDex[idx];
    }
 
    // 거꾸로 탐색하여 저장했으므로 거꾸로 다시 거꾸로 출력합니다
    for (int i = idx2 - 1; i >= 0; i--)
        printf("%d ", result[i]);
 
    return 0;
}