1074] Longest Ordered Subsequence (LIS)

문제설명:

연속적으로는 아니지만 인덱스가 증가하는 방향으로 제일 긴 증가수열을 만드는 문제이다

Longest increasing subsequence 문제를 해결하는 방법은 두가지가 있다.

1. 의 시간 복잡도를 가지는 단순 dp

2. 의 시간 복잡도를 가지는 binary search를 이용한 방법

문제링크 [1074 : Longest Ordered Subsequence]

첫번째 방법은 "dp[i] : i번째 원소를 보았을때 만들 수 있는 가장 긴 길이"로 상태공간을 잡고, 시간 내에 풀어내는 동적 계획법이다.

말그대로 i번째 수를 보았을 때는, j (i ... i-1) 번째 수 중 자신보다 작은 수가 존재했을 때, 

dp[j]+1 과 dp[i]를 비교해서 큰 쪽을 택하면 된다.

첫번째 방법

#include <stdio.h>
#include <algorithm>
using namespace std;

int ary[1001],dp[1001];

int main()
{
    int ary[1001];
    int dp[1001] = { 0 };
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++)scanf("%d", &ary[i]);
    for (int i = 0; i < n; i++)
    {
        dp[i] = 1;
        for (int j = 0; j < i; j++)
            if (ary[j] < ary[i])
                dp[i] = max(dp[i], dp[j] + 1);
    }
    
    int ans = 0;
    for (int i = 0; i < n; i++)ans = MAX(ans, dp[i]);
    printf("%d\n", ans);
    return 0;
}

두번째 방법의 경우 binary search를 이용해서 해결한다.

상태공간의 의미가 살짝 달라지는데, "dp[i] : 현재까지의 수들을 보았을때, lis를의 길이를 i로 만들 수 있는 가장 작은 수" 가 된다.

무슨 말이냐면, 만약 배열이 1 4 5 2 이라면 최장 증가 수열은 1 4 5 로 길이가 3이겠지만

lis 배열에서는 1 2 5 로 마찬가지로 길이는 3이지만 실제로 1 2 5로 증가하는 것은 아니다.

두번째 방법

#include <stdio.h>

int ary[1001], res[1001], n;

int lis(int v)
{
    int l = 0, r = n - 1,mid;
    while (l <= r)
    {
        mid = (l + r) / 2;
        if (v < res[mid])r = mid - 1;
        else if (v >res[mid]) l = mid + 1;
        else return -1;
    }
    return l;
 
}
int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i++)scanf("%d", &ary[i]);
    for (int i = 0; i < n; i++)res[i] = 10001;
    res[0] = -1;
     
    for (int i = 0; i < n; i++)
    {
        int idx = lis(ary[i]);
        if (idx == -1)continue;
        else res[idx] = ary[i];
    }
    int cnt;
    for (cnt = 0; cnt < n; cnt++)
        if (res[cnt] == 10001)break;
    printf("%d\n", cnt-1);
    return 0;
}