챕터3-15. DP | 문제 풀이3 - (4) 백준 No.11054 : 가장 긴 바이토닉 부분 수열

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

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

문제요약

수열 A가 주어졌을 때, 가장 긴 바이토닉 부분 수열의 길이를 구하는 문제
부분 수열이란?  수열에서 일부를 선택한 수열이다.
ex) A = {1 5 2 1 4 3 4 5 2 1}
      가장 긴 바이토닉 부분 수열 A = {1, 5, 2, 1, 4, 3, 4, 5, 2, 1}
      => 길이는 7

해결 방법

* 최근에 푼 3개의 문제에 대한 이해가 있다면 이를 응용하여 풀 수 있다.
- 바이토닉 수열의 꼭지값을 기준으로 왼쪽은 가장 긴 증가하는 부분 수열, 오른쪽은 가장 긴 감소하는 부분 수열을 찾아
   이 둘의 길이를 합하여 구할 수 있다.

   이를 조금만 다르게 생각해보면 

   "부분 수열의 마지막 원소로 A[i]를 꼭 포함하는 왼->오 방향으로 가장 긴 증가하는 부분 수열의 길이"
   + "부분 수열의 마지막 원소로 A[i]를 꼭 포함하는 오->왼 방향으로 가장 긴 증가하는 부분 수열의 길이"
   - 1 을 하여 구할 수 있다. (둘을 더했을 때 꼭지값에서 중복이 일어나므로 둘을 더한 값에서 1을 빼줘야 한다.)

<Bottom-up 방식>

(1) 구현
-> 'for문을 이용한 반복문'으로 구현

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int main()
{
    int n;
    cin >> n;

    vector<int> a(n);
    vector<int> d1(n);
    vector<int> d2(n);

    for (int i = 0; i < n; i++)
        cin >> a[i];


    // 왼->오 순으로 A[i]를 원소로 포함하는 가장 긴 증가하는 부분 수열의 길이 구하기
    for (int i = 0; i < n; i++)
    {
        d1[i] = 1;

        for (int j = 0 ; j < n; j++)
        {
            if (a[j] < a[i] && d1[i] < d1[j]+1)
                d1[i] = d1[j]+1;
        }
    }

    // 오->왼 순으로 A[i]를 원소로 포함하는 가장 긴 증가하는 부분 수열의 길이 구하기
    for (int i = n-1; i >= 0; i--)
    {
        d2[i] = 1;

        for (int j = n-1 ; j > i; j--)
        {
            if (a[j] < a[i] && d2[i] < d2[j]+1)
                d2[i] = d2[j]+1;
        }
    }


    int ans = d1[0] + d2[0] - 1;

    for (int i = 0; i < n; i++)
    {
        if (ans < d1[i] + d2[i] - 1)
            ans = d1[i] + d2[i] - 1;
    }

    cout << ans << "\n";
}

 

(2) 시간복잡도
= for 문의 반복 횟수 

이 방법을 사용하면 N개의 칸을 채워야 하고, 한칸 D[i]의 값을 채울 때 A[i]번을 A[1] ~ A[i-1]번과 모두 비교하므로 
시간복잡도는 N * O(N) = O(N^2)이 된다.