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

백준 11053

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

수열의 길이와 수열의 값을 입력받아  가장 긴 증가하는 부분수열을 구하는 문제이다.

 

이 문제 역시 DP 문제 이므로, d[i]를 구하는 것이 중요한데,

1. d[1] = 1
2. d[i]와 d[i-1] ~ d[1]의 관계 ← 이 부분에서 주의해서 살펴보았다.

'가장 긴 증가하는 부분수열' 이 되기 위해서는

앞에 있는 수 중 i번째 숫자보다 작으며, d의 값이 가장 큰 것을 찾아야 한다.

그 이후에는, 그 값(d[j])에 1을 더하면, 우리가 구해야 하는 d[i]값이 나온다. 

 

해당 내용에 맞추어 코드를 짜면 아래와 같다. 

#include <cstdio>

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

int main(void)
{
    d[0] = 1;
    int num;
    int biggest = 0;
    scanf("%d", &num);
    for (int i = 0; i < num; i++)
    {
        scanf("%d", &nums[i]);
    }

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

        if (biggest < d[i])
            biggest = d[i];
    }
    printf("%d", biggest);
}