글 읽기 - 최장감소함수 lower_bound 이용해서 푸는 방식..

nisroeld99 8년 전 0

처음에 문제보고

부등호바꾸고

upper_bound로 바꿔주기만하면되는거아닌가?

라고생각했다가 피봤씁니다. (STL 제대로 알고써야겠더라고요 ㅠㅠ)

결국은 그냥 input받을때, -1 을 곱해줘서

평범한 LIS 구하듯이 구했습니다만은

O(n^2) 은 배제하고

input값 조정하지않고 바로 푸는 방법은 없나요? (upper_bound lower_bound 등 이용해서 )

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

int a[1111];
int d[1111];
int main(){
    int n ;
    cin >> n ;
    
    for (int i = 1; i <= n ; i++){
        scanf("%d",&a[i]);
        a[i]*=-1;
    }
    
    
    int size=1;
    d[1]=a[1];
    
    for (int i =2 ; i<=n ; i++ ){
        if (a[i]>d[size]){
            size++;
            d[size]=a[i];
        }
        else {
            int next=lower_bound(d+1, d+size,a[i] ) -d ;
            d[next] = a[i];
        }
    }
    
    
    
    cout<<size<<endl;
    
    
}

yukariko 8년 전 1

lower_bound에 비교함수를 넣어주면 됩니다. 기본 비교함수가 less 이니 greater를 넣어주면 되겠네요.

nisroeld99 8년 전 0

감사합니다

@yukariko 님

lower_bound 류도 greater less가 적용이 되네요

또 배워갑니다

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

최장감소함수 lower_bound 이용해서 푸는 방식..

nisroeld99 8년 전 0

yukariko 8년 전 1

nisroeld99 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말