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

문제 설명

수열 S가 어떤 수 Sk를 기준으로 S1 < S2 < ... Sk-1 < Sk > Sk+1 > ... SN-1 > SN을 만족한다면, 그 수열을 바이토닉 수열이라고 한다.

예를 들어, {10, 20, 30, 25, 20}과 {10, 20, 30, 40}, {50, 40, 25, 10} 은 바이토닉 수열이지만,  {1, 2, 3, 2, 1, 2, 3, 2, 1}과 {10, 20, 30, 40, 20, 30} 은 바이토닉 수열이 아니다.

수열 A가 주어졌을 때, 그 수열의 부분 수열 중 바이토닉 수열이면서 가장 긴 수열의 길이를 구하는 프로그램을 작성하시오.

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

---

 

 

 

 

 

 

제한 사항

---

 

 

 

 

 

 

풀이

문제를 요약하면, 증가하였다 감소하는 수열을 바이토닉 부분 수열이라 한다.

주어진 수열에서 가장 긴 바이토닉 부분 수열을 구하면 된다.

 

해당 문제는 가장 긴 증가 수열을 구하는 문제에서 확장하여 구할 수 있다.

가장 긴 증가 수열을 구하는 문제는 k를 끝으로 하는 부분 수열의 길이를 갱신하며 진행하면 된다.

바이토닉 부분 수열은 감소하는 것을 포함하기 때문에 하나의 과정이 더 필요하다.

감소하는 수열은 반대에서 진행하여 증가하는 것과 같다.

예를 들어 보자.

빨간 부분인 [1, 2, 3, 4, 5] 까지는 증가하는 부분 수열과 같다.

5이후인 [5, 2, 1]은 맨끝에서 진행한 증가하는 부분 수열과 같다.

 

즉, 방향을 달리하여 증가하는 부분 수열의 길이를 구하면 된다.

for (int k = 0; k < N; k++)
{
    dp[k][0] = 1;
    for(int i = 0 ; i < k; i++)
    {
        if (Nums[i] < Nums[k])
        {
            dp[k][0] = max(dp[k][0], dp[i][0] + 1);
        }
    }
}

for (int k = N-1; k >= 0; k--)
{
    dp[k][1] = 1;
    for (int i = N-1; i > k; i--)
    {
        if (Nums[i] < Nums[k])
        {
            dp[k][1] = max(dp[k][1], dp[i][1] + 1);
        }
    }
}

 

그리고, 각 위치에서 두 개의 부분 수열의 개수의 합이 가장 큰 수가 정답이 된다.

이때, 해당 칸이 왼쪽, 오른쪽에 모두 포함되어 있기 때문에 1을 빼주어야 한다.

위의 예시에서 5가 이에 해당한다.

int Answer = 0;
for (int i = 0; i < N; i++)
{
    Answer = max(Answer, dp[i][0] + dp[i][1]);
}

cout << Answer-1 << endl;

---

 

 

 

 

 

전체 코드

#include <stdio.h>
#include <cstring>
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <cmath>
#include <climits>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>

using namespace std;

int N;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> N;
    vector<int> Nums(N, 0);
    vector<vector<int>> dp(N, vector<int>(2, 0));

    for (int i = 0; i < N; i++)
    {
        cin >> Nums[i];
    }

    for (int k = 0; k < N; k++)
    {
        dp[k][0] = 1;
        for(int i = 0 ; i < k; i++)
        {
            if (Nums[i] < Nums[k])
            {
                dp[k][0] = max(dp[k][0], dp[i][0] + 1);
            }
        }
    }

    for (int k = N-1; k >= 0; k--)
    {
        dp[k][1] = 1;
        for (int i = N-1; i > k; i--)
        {
            if (Nums[i] < Nums[k])
            {
                dp[k][1] = max(dp[k][1], dp[i][1] + 1);
            }
        }
    }

    int Answer = 0;
    for (int i = 0; i < N; i++)
    {
        Answer = max(Answer, dp[i][0] + dp[i][1]);
    }

    cout << Answer-1 << endl;

    return 0;
}

---