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

백준 14002

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

앞에서 작성했던 가장 긴 증가하는 부분 수열의 심화버전의 문제이다. (이전문제는 아래 링크로 들어가면 된다)

2020/07/22 - [백준 문제풀이] - 가장 긴 증가하는 부분 수열_ 백준11053

위 문제에서 조금 더 어려워 진 점은, 가장 긴 증가하는 부분 수열을 출력해야하는 점이다.

 

즉, 수열의 순서를 저장할 필요가 있는 것인데, 나는 11053 문제의 코드에 더 덧붙이는 방식으로 풀었으므로 (두 문제의 연관성이 크므로, 이 순서로 푸는 것을 추천한다) 11053 문제에서 생각했던 점화식의 흐름에 초점을 맞추어 진행했다.

 

각각의 부분수열을 저장할 수는 없으므로, d[i]를 구하면서, 하나의 배열을 추가하여 그 흐름을 활용하는 것이 필요하다.

즉, 가장 긴 부분수열을 찾는 과정에서 우리는 d[i]앞에 이어지는 부분인 d[j]를 찾으므로,

i앞에 오는 j를 prev 배열에 저장하고 그것을 역순으로 찾아가면 가장 긴 증가하는 부분수열을 찾을 수 있게 되는 것이다.

 

 

다만, 나같은 경우는 이러한 논리를 세워 문제를 풀었음에도 몇번 틀렸는데, 

추가적인 테스트케이스를 서치해서 돌린 이후에 코드를 수정했다.

4

4 1 2 3

[답 :: 3, 1 2 3]

 

4

1 3 4 2

[답 :: 3, 1 3 4]

 

6

4 5 6 1 2 3

[답 :: 3, 1 2 3] (오른쪽 1 2 3은 4 5 6이 될 수 도있고 여러 답이 될 수 있다.

 

6

4 9 11 5 7 8 

[답 :: 4, 4 5 7 8]

 

8

1 6 2 5 7 3 5 6

[답 :: 5, 1 2 3 5 6]

 

9

3 1 2 4 7 5 6 8 10

[답 :: 7, 1 2 4 5 6 8 10]

출처: https://www.crocus.co.kr/681 [Crocus]

또한, 나는 배열에 다시 넣어서 역순으로 출력했는데, 사실 스택으로 하는 것이 더 효율적인 방법으로 보인다. 

편하다고 계속 배열을 쓰는 버릇을 고치는게 필요할 것 같다. 

#include <cstdio>

using namespace std;
int nums[1001];
int d[1001];
int prev[1001];
int result[1001];

int main(void)
{
    int num;
    int biggest = 0;
    int idx = 0;

    int count = 0;
    int p;
    scanf("%d", &num);
    for (int i = 0; i < num; i++)
    {
        scanf("%d", &nums[i]);
    }

    for (int i = 0; i < num; i++)
    {
        d[i] = 1;
        prev[i] = i;
        for (int j = 0; j < i; j++)
        {
            if (nums[j] < nums[i] && d[i] < d[j] + 1)
            {
                d[i] = d[j] + 1;
                prev[i] = j;
            }
        }

        if (biggest < d[i])
        {
            idx = i;
            biggest = d[i];
        }
    }

    printf("%d\n", biggest);

    for (p = idx; p != prev[p]; p = prev[p])
        result[count++] = nums[p];
    result[count] = nums[p];

    for (int i = count; i > -1; i--)
    {
        printf("%d ", result[i]);
    }
}