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

백준의 가장 긴 바이토닉 부분 수열(11054) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

바이토닉 수열이라는 것은, 특정 값을 기준으로 좌측은 오름차순으로, 우측은 내림차순으로 정렬되어 있는 수열을 의미한다.

그럼 우리는 바이토닉 수열을 위에서 말한대로 2부분으로 나눠서 생각해볼 수가 있다.

1. 증가하는 부분 수열

2. 감소하는 부분 수열

이렇게 생각할 수가 있다. 왜 ?? 어차피 특정 Index를 기준으로 좌측은 '오름차순' 정렬이기 때문에, 이는 증가하는 부분 수열이라는 것을 의미하고, 우측은 '내림차순' 정렬이기 때문에, 이는 감소하는 부분 수열이라는 것을 의미한다.

그래서 ! 이 문제를 풀기전에, 먼저 풀어보고 왔으면 하는 문제들이 있다.

아래의 링크가 걸려있는 2문제는 꼭 먼저 풀어보고 오는 것을 권장한다. 풀이까지 보고 오는것도 !

[ 백준 - 가장 긴 증가하는 부분 수열(11053) 문제 바로가기 ]

[ 백준 - 가장 긴 감소하는 부분 수열(11722) 문제 바로가기 ]

[ 백준 - 가장 긴 증가하는 부분 수열(11053) 풀이 바로가기 ]

[ 백준 - 가장 긴 감소하는 부분 수열(11722) 풀이 바로가기 ]

위의 2문제를 풀어보고 풀이까지 보고 오는 것을 권장한다.

이 문제는 위의 2가지를 합쳐주기만 하면 된다.

먼저, "가장 긴 증가하는 부분 수열" 문제를 풀 때, 구했던 방법과 동일하게 전체 N개의 데이터에 대해서 증가하는 부분 수열의 크기를 구하는 것이다.

두 번째는, "가장 긴 감소하는 부분 수열" 문제를 풀 때, 구했던 방법과 동일하게 전체 N개의 데이터에 대해서 감소하는 부분 수열의 크기를 구하는 것이다.

여기까지 진행한다면, 우리는 N개의 데이터들에 대해서 각각이 갖는 [ 가장 긴 증가하는 부분 수열의 길이 , 가장 긴 감소하는 부분 수열의 길이 ] 를 구했을 것이다.

그럼 바이토닉 수열 중 가장 길이가 긴 것은 ??

N개의 데이터들이 갖는 위의 2개의 값을 더했을 때, 가장 길이가 긴 수열이 가장 긴 바이토닉 부분 수열의 길이가 될 것이다.

그런데 ! 마지막 정답을 도출하기 전에는 한가지 고려해줘야 할 것이 있다.

[ 1 , 2 , 3 , 4 , 3 , 2 , 1 ] 이라는 수열이 주어졌다고 가정해보자.

위의 수열에서는 정가운데 있는 '4'라는 숫자를 기준으로 길이가 7인 바이토닉 부분 수열이 존재한다.

그럼, 위에서 구했던 대로 '4'에 대한 증가하는 그리고 감소하는 부분 수열의 길이를 구해보자.

먼저, 증가하는 부분 수열의 길이는 [ 1 , 2 , 3 , 4 ] 로 길이가 4가 될 것이다.

두번째로, 감소하는 부분 수열의 길이는 [ 4 , 3 , 2 , 1 ] 로 길이가 4가 될 것이다.

그럼 4 + 4 = 8 ! 이라는 바이토닉 수열의 길이를 구할 수가 있는데, 정답이 아닌 것을 알 수가 있다.

우리가 눈으로 계산했을 때는 , 7이 나왔는데, 위와 같이 계산하면 8이 나오는 것이다.

왜냐하면 ! '4'가 중복되어서 계산되었기 때문이다.

[ 1 , 2 , 3 , 4 ] 에서 '4'가 한번 계산되어지고, [ 4 , 3 , 2 , 1 ] 에서 '4'가 한번 더 계산되어지기 떄문에 잘못된 결과값이 나오는 것이다.

즉 ! 바이토닉 수열의 길이는 "증가하는 부분수열의 길이 + 감소하는 부분수열의 길이 - 1" 을 해줘야 정확한 길이를 구할 수 있는 것이다.

[ 소스코드 ]

#include <iostream>
 
#define endl "\n"
#define MAX 1010
using namespace std;
 
int N;
int Arr[MAX];
int DP[MAX];
int DP2[MAX];
 
int Max(int A, int B) { if (A > B) return A; return B; }
 
void Input()
{
    cin >> N;
    for (int i = 1; i <= N; i++) cin >> Arr[i];
}
 
void Solution()
{
    for (int i = 1; i <= N; i++)
    {
        DP[i] = 1;
        for (int j = 1; j < i; j++)
        {
            if (Arr[i] > Arr[j])
            {
                DP[i] = Max(DP[i], DP[j] + 1);
            }
        }
    }
    for (int i = N; i >= 1; i--)
    {
        DP2[i] = 1;
        for (int j = N; j > i; j--)
        {
            if (Arr[i] > Arr[j])
            {
                DP2[i] = Max(DP2[i], DP2[j] + 1);
            }
        }
    }
 
    int Answer = 0;
    for (int i = 1; i <= N; i++)
    {
        Answer = Max(Answer, DP[i] + DP2[i]);
    }
    Answer = Answer - 1;
    cout << Answer << endl;
 
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
//    freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}