[11053] 가장 긴 증가하는 부분 수열

https://www.acmicpc.net/problem/11053

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

<문제>

dp를 사용하면 O(N^2)의 시간복잡도를 갖는다. dp는 다음과 같이 구성하면 된다.

dp[i] = i번째 수까지의 최대 길이

 

다만 이문제는 이분탐색을 사용하면 O(NlogN)만에도 해결이 가능하다.

비슷한 문제가 많은데, 대략 아래와 같은 구성을 갖는다.

가장 긴 증가하는 부분수열 : O(N^2), dp로 해결한다.
가장 긴 증가하는 부분수열 2,3 : O(NlogN), 이분탐색으로 해결한다. 
가장 긴 증가하는 부분수열 4 : O(N^2), DP + 최적해역추적
가장 긴 증가하는 부분수열 5 : O(NlogN), 이분탐색 + 최적해역추적

1,2,3은 최적해를 찾고,

4,5는 최적해 + 최적해 역추적 문제이다.

 

 

아래는 DP로 해결한 O(N^2) 코드이다.

<소스코드>

#include<stdio.h>
#include<algorithm>
using namespace std;
int main(void) {
    int a[1001] = { 0 }, n, i,j, dp[1001] = { 0 };
    scanf("%d", &n);
    for (i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        dp[i] = 1;
    }
    for (i = 1; i <= n-1; i++) {
        for (j = i + 1; j <= n; j++) {
            if (a[i] < a[j]) {
                dp[j] = max(dp[j],dp[i] + 1);
            }
        }
    }
    int max = 0;
    for (i = 1; i <= n; i++) {
        if (max < dp[i])
            max = dp[i];
    }
    if (max == 0)max = 1;
    printf("%d", max);
    return 0;
}