티스토리 뷰

728x90

https://www.acmicpc.net/problem/11054

 

11054번: 가장 긴 바이토닉 부분 수열

첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000)

www.acmicpc.net

동적계획법 C++

가장 긴 바이토닉 부분 수열 문제

 

접근 방법

가장 긴 증가하는 부분 수열과 가장 긴 감소하는 부분 수열이 중첩된 문제

0부터 i 까지의 가장 긴 증가하는 부분 수열을 구하고, i 부터 n까지 감소하는 부분 수열을 구하여 합한 값으로 구한다.

증가하는 부분 수열은 차이가 없지만, 감소하는 부분 수열은 원래는 i까지 감소하는 부분수열을 구했었는데

여기선 i부터 n까지 감소하는 부분 수열을 구한다는 점이 다르다.

 

소스코드

#include <iostream>
using namespace std;

int main(){
    int n;
    cin >> n ;

    int num[n];
    int lengthasc[n];
    int lengthdesc[n];
    int result = 0;
    for(int i = 0 ; i < n ; i++){
        cin >> num[i];
    }
    for(int i = 0 ; i < n ; i++){
        lengthasc[i] = 1;
        for(int j = 0 ; j < i ; j++){
            if(num[j] < num[i] && lengthasc[j] >= lengthasc[i]){
                lengthasc[i] = lengthasc[j]+1;
            }
        }
    }
    
    for(int j = n-1 ; j >= 0 ; j--){
        lengthdesc[j] = 1;
        for(int k = j+1 ; k < n ; k++){
            if(num[j] > num[k] && lengthdesc[j] <= lengthdesc[k]){
                lengthdesc[j] = lengthdesc[k]+1;
            }
        }
    }

    for(int i = 0 ; i < n ; i++){
        if(result < lengthdesc[i]+lengthasc[i]-1)
            result = lengthdesc[i]+lengthasc[i]-1;
    }
    
    cout << result;
    
    return 0;
}
728x90
250x250
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
«   2024/02   »
1 2 3
4 5 6 7 8 9 10
11 12 13 14 15 16 17
18 19 20 21 22 23 24
25 26 27 28 29
글 보관함