[BOJ] 가장 긴 바이토닉 부분 수열(11054)

[백준(BOJ)] 가장 긴 바이토닉 부분 수열(11054) C++

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

문제 설명

DP

기존의 증가하는 수열, 감소하는 수열이 합쳐진 문제입니다.

수열이 증가하다가 감소가 되는 경우, 수열이 계속 증가하는 경우, 수열이 계속 감소하는 경우가 모두 바이 토닉 부분 수열입니다.

수열이 감소하다가 증가하는 경우는 해당되지 않습니다.

DP를 활용해 해결할 수 있었습니다.

---

Solution

앞서 언급한 세 가지 경우로 나누어서 DP 배열에 갱신해 주어야 합니다.

• 수열이 계속 증가하는 경우 -> dp[0][현재 인덱스]
• 수열이 증가하다가 감소가 되는 경우 -> dp[1][현재 인덱스]
• 수열이 계속 감소하는 경우 -> dp[2][현재 인덱스]

로 만들어 값을 계속 비교해 아합니다.

이때, 계속 증가하거나 감소하는 값은 max(현재 인덱스의 dp 값, 증가하거나 감소하는 부분의 dp 값 + 1)로 계속 갱신을 해주면 됩니다.

그러나 증가하다가 감소로 바뀌는 수열의 경우,

• 현재 인덱스에서 계속 증가했을 때의 경우의 수
• 현재 인덱스가 증가하다가 감소로 변했다고 했을 때의 DP 크기를 수를 비교하며 갱신해 줘야 합니다.

---

#include <iostream>
#include <algorithm>
using namespace std;
int n, result;
int dp[3][1001];
int val[1001];
int main(void){
    cin >> n;
    for(int i=1;i<=n;i++){
        cin >> val[i];
        dp[0][i]=1;
        dp[1][i]=1;
        dp[2][i]=1;
    }
    for(int i=1; i<=n;i++){
        for(int j=1; j<i;j++){
            if(val[j]<val[i]){
                dp[0][i]= max(dp[0][i], dp[0][j]+1 );
            }
            if(val[j]>val[i]){
                dp[2][i] = max(dp[2][i],dp[2][j]+1);
                dp[1][i] = max(dp[1][i],dp[0][j]+1);
                dp[1][i] = max(dp[1][i],dp[1][j]+1);
            }
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1; j<3;j++){
            result = max(result,dp[j][i]);
        }
    }
    cout << result << '\n';
    return 0;
}