[백준 11054] 가장 긴 바이토닉 부분 수열

0. 제목

• 백준 11054 가장 긴 바이토닉 부분 수열
• BOJ 11054 가장 긴 바이토닉 부분 수열
• C++ 11054 가장 긴 바이토닉 부분 수열

---

1. 문제

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

---

2. 풀이

• DP 방식을 이용하였다.
• 가장 긴 증가하는 부분 수열을 앞에서부터 한 번, 뒤에서부터 한 번 실시하면 된다.
• 먼저 모든 dp[i] 값을 나올수 있는 최소값인 1로 초기화 시킨다.
• dp[i]를 구하기 위해서는 다음과 같은 과정을 거쳐야 한다. 해당 인덱스의 배열 값(A[i])과 그 이전 값들을 비교한다. A[i]가 이전 값들보다 크면 1씩 증가해주면 된다고 생각할 수 있다.
• 그러나 그렇게 하면 오류가 발생한다. 각각의 전 dp값들과 비교하지만 dp[i] < dp[j] + 1 (j는 1부터 i-1까지)을 만족해야한다. 작은 수로 갱신이 되면 안되기 때문이다.
• 이 과정을 앞에서부터 한번, 뒤에서부터 한번 거친 후, 각각의 인덱스에서의 앞에서 부터의 증가수열 값, 뒤에서 부터의 증가수열 값을 더한 후 겹치는 인덱스 즉, 1을 빼주면 가장 긴 바이토닉 부분 수열의 길이를 구할 수 있다.

---

3. 코드

#include <iostream>
using namespace std;
 
int main(int argc, const char * argv[]) {
    int N;
    int A[1001];
    int dp[2][1001];
    
    cin >> N;
    for(int i = 1; i <= N; i++){
        cin >> A[i];
    }
    
    //처음부터 시작
    for(int i = 1; i <= N; i++){
        dp[0][i] = 1;
        for(int j = 1; j < i; j++)
            if(A[i] > A[j] && dp[0][i] < dp[0][j] + 1)
                dp[0][i] = dp[0][j] + 1;
    }
    
    //끝에서부터 시작
    for(int i = N; i >= 1; i--){
        dp[1][i] = 1;
        for(int j = N; j > i; j--)
            if(A[i] > A[j] && dp[1][i] < dp[1][j] + 1)
                dp[1][i] = dp[1][j] + 1;
    }
    
    int max = 0;
    for(int i = 1; i <= N; i++){
        if(max < dp[0][i] + dp[1][i] - 1)
            max = dp[0][i] + dp[1][i] - 1;
    }
    
    cout << max << '\n';
    
    return 0;
}