백준 #11054. 가장 긴 바이토닉 부분 수열

백준 #11054. 가장 긴 바이토닉 부분 수열

정리

• 이 문제의 경우 앞에서 해결한 ‘백준 #11053. 가장 긴 증가하는 부분 수열' 문제에서 풀이의 힌트를 얻어 진행했다. (링크 참고)

• ‘바이토닉 수열'은 어떤 수 Sk를 기준으로, 왼쪽은 ‘증가하는 부분 수열', 오른쪽은 ‘감소하는 부분 수열'이라는 특징이 있다. 따라서 두 부분을 나눠서 각각 동적 계획법으로 구하였다.

• 답을 구할 때는 앞에서 구한 두 부분을 더한 값이 최대인 것을 구했다. (앞에서 증가/감소하는 수열의 길이를 구할 때 가운데 값이 양쪽에 모두 포함되게 구하였으므로 전체 수열의 길이를 구할 때는 1을 빼 줘야 한다.)
  
  

정답 코드

#include <iostream>
#include <algorithm>

using namespace std;

int main(void) {
    int N;
    int A[1001];       // 입력으로 주어지는 수열 A
    int dp[1001][2];   // 가장 긴 바이토닉 수열의 길이 저장
    int res = 0;
    
    cin>>N;
    for(int i=1; i<=N; i++) {
        cin>>A[i];
        dp[i][0] = 1;
        dp[i][1] = 1;
    }
    
    dp[1][0] = 1;       // dp[][1] : 증가하는 부분 수열의 길이
    dp[N][1] = 1;       // dp[][2] : 감소하는 부분 수열의 길이
    for(int i=2; i<=N; i++) {
        for(int j=1; j<=i; j++) {
            if (A[i] > A[j]) {
                dp[i][0] = max(dp[j][0] + 1, dp[i][0]);
            }
        }
    }
    // 각 index에서 가장 긴 증가하는 부분 수열의 길이를 dp로 구한다.
    
    for(int i=N-1; i>=1; i--) {
        for(int j=i; j<=N; j++) {
            if (A[i] > A[j]) {
                dp[i][1] = max(dp[j][1] + 1, dp[i][1]);
            }
        }
    }
    // 각 index에서 가장 긴 감소하는 부분 수열의 길이를 dp로 구한다.
    
    for(int i=1; i<=N; i++) {
        res = max(res, dp[i][0] + dp[i][1] - 1);
    }
    // 증가하는 부분 수열 + 감소하는 부분 수열의 값이 가장 긴 것이 정답이다.
    
    cout<<res<<endl;
    
    return 0;
}