[백준] 11054번: 가장 긴 바이토닉 부분 수열 풀이 및 해설(C++)

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

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

 

 

풀이

이 문제를 보고 가장 먼저 생각난 것은 바이토닉 수열의 중앙점이다

S1 < S2 <... Sk-1 < Sk > Sk+1 > ... SN-1 > SN에서 Sk를 말하는 것이다. Sk를 어디로 S1~SN 중 어디로 할지 정하고,

S1~SK에서 나오는 증가하는 부분수열의 개수+ SK~SN에서 나오는 감소하는 부분수열의 개수를 K 값에 따라 비교해 최댓값을 출력하면 된다.

 

2023.06.11 - [algorithm/dp] - [백준] 11053번: 가장 긴 증가하는 부분 수열 풀이 및 해설(C++)

[백준] 11053번: 가장 긴 증가하는 부분 수열 풀이 및 해설(C++)

가장 긴 증가하는 부분수열 풀이는 다음과 같다.

 

아래의 해답 코드에서

dp [i]는 i를 중앙점으로 했을 때 arr [0]~arr [i]까지 가장 긴 증가하는 부분수열의 길이이며

dp2 [n-i-1]은 i를 중앙점으로 했을 때 arr [i] ~arr [n-1]까지 가장 긴 감소하는 부분수열의 길이이다.

 

beforemax와 beforemax2는 가장 긴 증가하는(감소하는) 부분수열에서 현재까지 그 길이의 최댓값이다.

 

해답 코드

#include <iostream>
#include <string>
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;

int main(){
    fastio;
    int n,max=1,beforemax,beforemax2;
    cin>>n;
    int arr[n];
    int arr2[n];
    int dp2[n];
    int dp[n];
    cin>>arr[0];
    dp[0]=1;
    dp2[0]=1;
    for(int i=1; i<n; i++){
        cin>>arr[i];
        beforemax=0;
        for(int j=i-1; j>-1; j--){
            if(arr[j]<arr[i] && beforemax<dp[j]){
                beforemax=dp[j];
            }
        }
        dp[i]=beforemax+1;
    }
    for(int i=0; i<n; i++){
        arr2[i]=arr[n-i-1];
    }
    for(int i=1; i<n; i++){
        beforemax2=0;
        for(int j=i-1; j>-1; j--){
            if(arr2[j]<arr2[i] && beforemax2<dp2[j]){
                beforemax2=dp2[j];
            }
        }
        dp2[i]=beforemax2+1;
    }
    for(int i=0; i<n; i++){
        int k=dp[i]+dp2[n-i-1]-1;
        if(k>max){
            max=k;
        }

    }
    
    cout<<max;

    
    return 0;
}

 

PLUS

가장 긴 증가하는 부분수열은 다른 문제에서도 많이 쓰이는 풀이법 같다. DP를 풀기 위해서는 숙지해야겠다.