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

출처 : www.acmicpc.net/problem/11053

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

 

고려사항

- lis 알고리즘 활용

- memo[idx] 의 idx 는 num[idx] 가 마지막 원소로 포함되어 있는 부분 수열 길이의 최대값.

- memo[idx]는 다음 두 가지 조건을 만족하는 경우와 그렇지 않은 경우로 나뉨.

1. tmp 는 1 ~ idx -1 사이의 값.

2. num[tmp] < num[idx] 를 만족.

위 두가지 조건을 만족하는 tmp 들 중 memo[tmp]가 최대값인 tmp 를 tmpMax 라 한다면,

memo[idx] = memo[tmpMax] + 1

 

- 다음 두 조건을 만족하지 못하는 경우에는 1, num[idx] 로만 이루어진 새로운 문자열임을 나타낸다.

- memo 가 완성되면 그 중 최대값을 출력!

=> n^2 로 그닥 빠른 알고리즘은 아님, 따라서 세그멘트 트리를 활용하거나 이분탐색을 이용해서 조금 더 빠른 nlogn 인

lis 알고리즘을 구현해 낼 수 있다고 한다.

 

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    int num[1000];
    int memo[1000];
    int n, ans=1;

    cin>>n;
    for(int i=0;i<n;++i){
        cin>>num[i];
    }

    for(int i=0;i<n;++i){
        memo[i] = 1;
        for(int j=0;j<i;++j){
            if(num[j] < num[i]){
                memo[i] = max(memo[i], memo[j]+1);
            }
        }
        ans = max(ans, memo[i]);
    }

    cout<<ans;

    return 0;
}