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

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

[ 문제 바로가기 ]

[ 문제풀이 ]

1) 이 문제는 쉽게말해서 하나의 수열에서 "가장 긴 증가하는 부분수열 + 가장 긴 감소하는 부분수열" 을 합쳐놓았을 때,

   가장 최대길이가 되는 수열을 찾는 문제이다.

   아직 풀지 않았다면, 이 문제를 풀고 풀어보면 좋을 것 같다.

   문제 구현의 전체적인 틀은 위에서 말한것과 같다.

   주어진 수열에서, 모든 원소들의 증가하는 부분수열의 크기와, 감소하는 부분수열의 크기를 구해서 더했을 때,

   최댓값이 되는 원소의 크기를 정답으로 도출해 내면 된다.

   그렇다면, 증가하는 부분수열을 구현하는 방법과, 감소하는 부분수열을 구현하는 방법을 따로따로 구체적으로 알아보자.

2) 증가하는 부분수열을 구하는 방법부터 알아보자.

   본인은 먼저, 증가하는 부분수열의 크기를 저장하는 DP[] 1차원 배열을 만들어서 사용하였다.

   DP[a] = b 의 의미는 "a번 Index의 원소의 증가하는 부분수열의 크기는 b입니다." 이다.

   또한, 초기 값은 모두 1이다. 왜냐하면, 어떤 원소를 선택하든, 자기자신인 '1'의 크기만큼은 가지기 때문이다.

   예를 들어서, { 1, 4, 7, 5, 3, 6 } 이라는 수열이 있다고 가정해보자.

   증가하는 수열을 구하는 방법을 순서대로 적어보고, 그 순서에 맞게 풀어보겠다.

   1. 자기보다 이전의 있는 원소들 중에서 더 작은 원소들을 찾는다.

   2. 그 원소를 선택했을 때, 현재 자기자신의 증가하는 부분수열의 크기 보다 1만큼 더 커진다면 값을 갱신 !

   위의 2가지 과정에 입각해서 차례차례 알아보자.

   [ 첫번째 원소 = 1 ]

   1번조건 - 자기보다 이전의 있는 원소들이 없으므로 1번조건에서 실행되는 부분이 없으므로 첫 번째 원소의 증가하는

   부분수열의 크기는 1이다.

   DP[1] = 1

   [ 두번째 원소 = 4 ]

   현재 DP[2] = 1 (DP[4] = 1이 아니라, 2번째 원소이므로 DP[2] = 1이다.)

   1번조건 - 자기보다 이전에 있는 원소 = { 1 } 중에서 더 작은 원소 { 1 }

   2번조건 - 1을 선택했을 때, 현재 자기자신의 증가하는 부분수열의 크기(DP[2]의 값) 가 1만큼 더 커지는가 ??

   1을 선택하게 되면, { 1, 4 } 가 되므로 크기가 2가된다. 즉, DP[2] = 1 보다 1만큼 더 커진 2가 된다 !

   그렇다면 DP[2]의 값을 '2' 로 갱신 ! 

   DP[2] = 2

   [ 세번째 원소 = 7 ]

   현재 DP[3] = 1

   1번조건 - 자기보다 이전에 있는 원소 = { 1, 4 } 중에서 더 작은 원소 = { 1, 4 }

   2번조건 - 먼저 원소 '1'을 선택했을 경우, 증가하는 부분수열이 { 1, 7 } 이 되므로, DP[3] = 1 의 값보다 1만큼 더커진

   DP[3] = 2가 된다. 그러므로 갱신 !

   현재 DP[3] = 2

   원소 '4'를 선택했을 경우, 증가하는 부분수열이 { 1, 4, 7 } 이 되므로, DP[3] = 2 의 값보다 1만큼 더커진 3이 된다.

   따라서 값을 갱신 !

   DP[3] = 3

   [ 네번째 원소 = 5 ]

   설명이 너무 길어지니, 지금부터는 위의 내용을 이해했다고 가정하고, 결과부터 말하겠다.

   { 1, 4, 5 } 로 DP[4] = 3이 될 것이다.

   [ 다섯번째 원소 = 3 ]

   { 1, 3 } 으로 DP[5] = 2

   [ 마지막 원소 = 6 ]

   { 1, 4, 5, 6 } 으로 DP[6] = 4 가 된다. 따라서, 가장 큰 증가하는 부분수열은 '4'가 된다.

  

   위와 같은 방식으로, 모든 원소들의 증가하는 부분수열의 크기를 구하자 !

   사실, 반대 케이스는 위와 반대로만 생각해주면 된다.

   자기 보다 이전에 있는 원소들이 아닌, 자기 보다 이후에 있는 원소들 중에서, 더 작은 원소들에 대해서만 똑같이 계산을

   해주자 ! 그렇게 되면 각 원소들의 증가하는 부분수열과, 감소하는 부분수열의 크기를 구할 수 있을 것이다.

  

   정답 도출은 모든 원소들의 (증가하는 부분수열의 크기 + 감소하는 부분수열의 크기) - 1 을 한 값중 최댓값이 정답이 된다.

   뒤에 -1은 왜해주는 것일까???

   바로 해당 원소가 중복이 되기 때문이다.

   예를 들어서 { 1, 2, 3, 2, 1 } 이라는 수열이 있다고 생각해보자.

   원소 '3'일 때, { 1, 2, 3 } 으로 증가하는 부분수열의 크기 = 3

   { 3, 2, 1 } 로 감소하는 부분수열의 크기 = 3 으로 바이토닉 부분수열의 크기는 3 + 3 = 6이 될 것이다.

   하지만, 여기서 증가하는 부분수열, 감소하는 부분수열에 '3'이라는 원소가 중복으로 사용되었기 때문이다.

   따라서 한 번만 계산해줘야 하고, 실제로도 정답은 { 1, 2, 3, 2, 1 } 로 크기가 5이다.

   그래서 -1을 해줘야 한다.

[ 소스코드 ]

#include<iostream>
 
#define endl "\n"
#define MAX 1001
using namespace std;
 
int N;
int Arr[MAX];
int DP[MAX];    // 앞에서부터 찾는 최장수열
int R_DP[MAX];    // 뒤에서부터 찾는 최장수열
 
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[j] < Arr[i] && DP[i] < DP[j] + 1)
            {
                DP[i] = DP[j] + 1;
            }
        }
    }
 
    for (int i = N; i >= 1; i--)
    {
        R_DP[i] = 1;
        for (int j = N; j >= i; j--)
        {
            if (Arr[i] > Arr[j] && R_DP[j] + 1 > R_DP[i])
            {
                R_DP[i] = R_DP[j] + 1;
            }
        }
    }
 
    int Answer = 0;
    for (int i = 0; i <= N; i++)
    {
        if (Answer < DP[i] + R_DP[i] - 1) Answer = DP[i] + R_DP[i] - 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;
}