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

LIS(Longest Increasing Sequence)

최장 증가 부분 수열 문제이다. 

lower_bound를 이용하여 문제를 풀이 할 수 있다. 

#include<cstdio>
#include<algorithm>
#define MAX 1001
using namespace std;
int a[MAX] = {0,};
int size;
// 10 20 10 30 20 50
//  1  2  1  2  1  2 
//  1  2  2  3  3  4
//  
// 10 20 10 11 12 50
//  1  2  1  2  3  4 // max 보다 작으면 초기화
//  1  2  2  2  2  3 
int b[MAX][3] = {{0,0,0},{1,1,0}};
 
int main(){
    scanf("%d", &size);
    for(int i = 1 ; i <= size ; i++){
        scanf("%d",&a[i]);
    }
 
    int max_1 = 1;
    for(int i = 2 ; i <= size ; i++){
 
        int cnt = 1;
        for(int j = i-1 ; j >= 1 ; j--){ // 이전을 탐색
            if( a[j] < a[i] ){ // 현재 수 보다 작은 수가 있을 때 
                if(cnt <  b[j][1]+1) cnt = b[j][1]+1; // 그때 카운트 된게 더 많거나 같다면 해당 카운트+1로 바꿈.
            }
            else if( a[j] == a[i] ){                
                if(cnt < b[j][1])    cnt = b[j][1];
            }
        }
        b[i][1] = cnt;
        max_1 = max(max_1,b[i][1]);
 
    }
 
    printf("%d",max_1);
 
    return 0;
}
 
 

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
 
typedef vector<int> VI;
 
int main(){
    int n;    
    scanf("%d", &n);
    VI num = VI(0);
    for(int i = 0 ; i < n ; i++){
        int input;
        scanf("%d", &input);
        num.push_back(input);
    } // input seq of num 
 
    VI seq = VI(0);
    seq.push_back(num[0]);
    for(int i = 1 ; i < n ; i++){
        int here = num[i];
        auto index = lower_bound(seq.begin(), seq.end(), here);
        
        if( index == seq.end() ) seq.push_back(here);
        else if( index < seq.end() )  *index = here;        
    }
 
    printf("%d", seq.size());
    
    return 0;
}