문제 11054 가장 긴 바이토닉 부분 수열 ( C++ )

문제 풀이

 

dp를 이용하여 오름차순으로 증가하는 부분 수열 중 가장 긴 수열의 길이를 찾고, 내림차순으로 감소하는 부분 수열 중 가장 긴 수열의 길이를 찾은 뒤 두 값을 합하고, -1을 해서 출력하면 풀 수 있는 문제이다.

 

 

1. 입력 받기

 

그냥 받아도 상관없지만 속도를 증가시키면서 입력을 받아보자

 

ios_base::sync_with_stdio(false);

cin.tie(NULL);

cout.tie(NULL);

 

세 줄로 입력을 조금이라도 빠르게 받을 수 있다.

 

int main (void) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    int n;
    cin >> n;
 
    for (int i = 1; i <= n ;i++)
        cin >> arr[i];
 
    solve(n);
 
    return 0;
}
 

for (int i = 1 ; i <= n ; i++) 
{
    front_dp[i] = 1;
 
    for (int j = 1 ; j <= i ; j++ ) 
    {
        if ( arr[j] < arr[i] && front_dp[i] < front_dp[j] + 1 ) 
        {
            front_dp[i] = front_dp[j] + 1;
        }
    }
}
 

 

 

3. 내림차순 부분수열 구하기

 

오름차순 부분수열과 비슷하다.

 

 

for (int i = n ; i >= 1 ; i--) 
{
    back_dp[i] = 1;
    
    for (int j = n; j >= i ; j--) 
    {
        if ( arr[i] > arr[j] && back_dp[j] + 1 > back_dp[i] ) 
        {
            back_dp[i] = back_dp[j] + 1;
        }
    }
}
 

 

 

4. 최대 길이 구하기

 

오름차순 부분수열 최장 길이, 내림차순 부분수열 최장 길이를 합한 값에 1을 빼야한다. 1을 빼는 이유는 중앙값이 중복되기 때문. 

예로, { 1, 2, 3 } , { 3, 2, 1} 이라면 3이 겹치므로 최장 길이 합에 1을 빼야함

 

 

 int ans = 0;
 
    for (int i = 0; i <= n ; i++ )
    {
        if ( ans < front_dp[i] + back_dp[i] - 1 )
            ans = front_dp[i] + back_dp[i] - 1;
    }
 
    cout << ans << endl;
 

 

#include <iostream>
 
using namespace std;
 
int arr[1001];
 
int front_dp[1001];
int back_dp[1001];
 
void solve(int n) {
 
    for (int i = 1 ; i <= n ; i++) {
        front_dp[i] = 1;
        for (int j = 1 ; j <= i ; j++ ) {
            if ( arr[j] < arr[i] && front_dp[i] < front_dp[j] + 1 ) {
                front_dp[i] = front_dp[j] + 1;
            }
        }
    }
 
    for (int i = n ; i >= 1 ; i--) {
        back_dp[i] = 1;
        for (int j = n; j >= i ; j--) {
            if ( arr[i] > arr[j] && back_dp[j] + 1 > back_dp[i] ) {
                back_dp[i] = back_dp[j] + 1;
            }
        }
    }
 
    int ans = 0;
 
    for (int i = 0; i <= n ; i++ )
    {
        if ( ans < front_dp[i] + back_dp[i] - 1 )
            ans = front_dp[i] + back_dp[i] - 1;
    }
 
    cout << ans << endl;
}
 
int main (void) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    int n;
    cin >> n;
 
    for (int i = 1; i <= n ;i++)
        cin >> arr[i];
 
    solve(n);
 
    return 0;
}