문제

image.png

image.png

풀이

 해당 문제는 가장 긴 증가하는 부분 수열 문제를 응용해서 해결 할 수 있다. 다만, 가장 긴 증가하는 부분 수열의 길이 이외에도 부분 수열을 출력해야 한다는 점에서 차이가 있다. v라는 배열을 생성한 후, v 에는 증가하는 부분 수열의 index 값을 저장 시킨다.

예를들어, 아래와 같은 형태로 수열이 입력되었다면
num에서 10과 20을 비교하면, 20은 10보다 커서 증가하는 부분 수열이다. dp[2] = 2가 된다. 따라서, v[2]에는 증가하기 전의 index값을 기록한다.

num[i] = {10,20,10,30,20,50}
dp[i] = {1,2,1,3,1,4}
v[i] = {0,1,0,2,3,4}

코드


#include<stdio.h>
int dp[1001];
int num[1001];
int v[1001];
int max = -2147000000;
void go(int p) {
    if(p == 0) return;
    go(v[p]);
    printf("%d ", num[p]);

}
// go(6) go(5), go(4), go(2)
// 10 20 30 50
int main() {

    int n;
    scanf("%d",&n);
    for(int i = 1; i <= n; i++) {
        scanf("%d",&num[i]);
    }
    for(int i = 1; i <= n; i++) {

        dp[i] = 1;
        for(int j = 1; j < i; j++) {
            if(num[i] > num[j] && dp[i] < dp[j]+1){
                dp[i] = dp[j] + 1;
                v[i] = j;
            }
        }

    }
    int p = 0;
    for(int i = 1; i <= n; i++) {
        if(max < dp[i]) {
            max = dp[i];
            p = i;
        }
    }
    printf("%d\n",max);
    go(p);
    printf("\n");
    return 0;
}