[BaekJoon] 11054. 가장 긴 바이토닉 부분 수열

11054. 가장 긴 바이토닉 수열 

Dynamic Programming문제이다.

이전에 풀었던 가장 긴 증가하는/감소하는 수열 문제를 응용하여 어렵지 않게 풀어낼 수 있었다.

 

입력받은 수열에 대하여 for문을 수행하며,

 1. 현 index에서의 arr[i]의 value가 앞선 index의 value보다 큰 값을 가지고 있고

 2. DP[i]의 value가 앞선 index j의 value와 작거나 같다면, DP[i]의 값을 1 증가시킨다

    for(i=0;i<cnt;i++){
        DP[i]=1;
        for(int j=0;j<i;j++){
            if(arr[i]>arr[j] && DP[i]<DP[j]+1){
                DP[i]++;
            }
        }
    }

 

다만, 이 바이토닉 수열의 경우, 가장 큰 수 Sk를 기점으로 다시 감소하는 부분을 고려해주어야 하기 때문에, 위와 같은 process를 배열의 맨 끝부터 앞까지 한 번 더 수행한다.

    for(i=cnt-1;i>=0;i--){
        decreasingDP[i]=1;
        for(int j=cnt-1;j>i;j--){
            if(arr[i]>arr[j] && decreasingDP[i]<decreasingDP[j]+1)
                decreasingDP[i]++;
        }
    }

 두 방향에서 구한 DP의 값들을 index별로 합친 값 중, 가장 큰 값에서 1을 뺀 값이 가장 긴 바이토닉 수열의 길이가 될 것이다

(가장 큰 value인 Sk에 대해서 한 번 중복되기 때문에 -1을 해주는 것이다)

 

전체 코드이다.

#include <stdio.h>
#include <stdlib.h>

int maxValue(int a,int b){
    return a>b ? a : b;
}
int increasingDP[1001] = {0,};
int decreasingDP[1001] = {0,};
int main(){

    int arr[1001]={0,};
    int i,cnt,n,max;
    
    scanf("%d",&cnt);
    
    for(i=0;i<cnt;i++){
        scanf("%d",&n);
        arr[i]=n;
    }
    
    for(i=0;i<cnt;i++){
        increasingDP[i]=1;
        for(int j=0;j<i;j++){
            if(arr[i]>arr[j] && increasingDP[i]<increasingDP[j]+1){
                increasingDP[i]++;
            }
        }
    }

    for(i=cnt-1;i>=0;i--){
        decreasingDP[i]=1;
        for(int j=cnt-1;j>i;j--){
            if(arr[i]>arr[j] && decreasingDP[i]<decreasingDP[j]+1)
                decreasingDP[i]++;
        }
    }
   
    max=0;
    for(i=0;i<cnt;i++)
        max=maxValue(max, increasingDP[i]+decreasingDP[i]);
    
    printf("%d\n",max-1);
    
    return 0;
}

 

---

➡︎ Binary Search를 이용한 LIS(Longest Increasing Subsequence) 탐색 

 - 시간 복잡도 O(NlogN)

 int main(){
 	...
 	idx=0;
    DP[0]=arr[0];
    for(i=1;i<cnt;i++){
        if(DP[idx]<arr[i]){
            DP[idx+1]=arr[i];
            idx++;
        }
        else{
            ans=lower_bound(idx,arr[i]);
            DP[ans]=arr[i];
        }
    }
	...
}

//binary search를 활용하여, DP에 수를 삽입할 위치를 찾는다
int lower_bound(int idx,int x){
    
    int i;
    for(i=0;i<idx;i++){
        if(DP[i]>=x) return i;
    }
    return idx;
}