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

문제 링크

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

11054번: 가장 긴 바이토닉 부분 수열

 

들어가기 전에...

문제를 해결한 이후에 다른 분들의 풀이를 보니 훨씬 더 효율적이고 간단하게 풀었음을 발견함...

주어진 크기 데이터가 1000개 이하였기 때문에 저처럼 \(O(n^{3})\)로도 풀 수 있었지만

더 효율적이고 간단한 풀이가 존재하기 때문에 이런 식으로 풀 수도 있구나~ 하는 정도로만 참고만 해주시길 ^,,,^

 

문제 설명

주어진 수열 S에 대해, 가장 긴 바이토닉 부분 수열의 길이를 구한다.

바이토닉 부분 수열이란 어떤 수 \(S_{k}\)를 기준으로

좌측의 숫자들은 가장 왼쪽에서부터 오름 차순으로, 우측의 숫자들은 \(S_{k}\) 이후로 내림 차순으로 정렬된 수열이다.

즉, {10, 20, 30, 25, 20}, {10, 20, 30, 40}, {50, 40, 25, 10} 은 바이토닉 수열이지만

{10, 20, 30, 40, 20, 30} 은 바이토닉 수열이 아니다.

 

첫 줄에 수열의 크기 N이 주어지며 둘째 줄에 수열 A를 이루고 있는 \(A_{i}\)가 주어진다.

수열 A의 부분 수열 중에서 가장 긴 바이토닉 수열의 길이를 출력한다.

 

사고 과정

N이 1000 이하이기 때문에 시간복잡도 측면에서 여유가 있다고 생각했다.

또한 이전 LIS 문제인 '가장 긴 증가하는 부분 수열'문제를 해결한 방법을 참고하였는데,

수열 A에서 어떤 수 \(S_{k}\)를 정한다면 그 당시의 가장 긴 바이토닉 수열을 구할 수 있었다.

 

예를 들어 백준의 입력 예시인 수열 {1, 5, 2, 1, 4, 3, 4, 5, 2, 1}에 대해 생각해보자.

\(S_{k}\)가 4번째 index인 4라고 한다면 해당 값을 기준으로 왼쪽과 오른쪽을 나누어

왼쪽에서부터 증가하는 가장 긴 부분 수열과 해당 값으로 부터 감소하는 가장 긴 부분 수열을

구함으로써, 즉, \(O(n^{2})\)의 알고리즘으로 가장 긴 바이토닉 부분 수열의 길이를 구할 수 있다.

 

해결 과정

수열 {1, 5, 2, 1, 4, 3, 4, 5, 2, 1}에 대해 \(S_{k}\)가 4번째 index인 4인 상황에 대해 살펴보자.

실제로는 \(S_{k}\)가 0번째 index부터 N-1번째 index까지 변경되며 아래의 과정을 반복하게 될 것이다.

 

우선 \(S_{k}\)를 기준으로 왼쪽과 오른쪽으로 나눈다.

이때 \(S_{k}\) Standard라 하자.

왼쪽에서는 Standard를 기준으로 좌측으로 값들을 선택해나가며 가장 긴 오름차순 수열을 구한다.

선택된 값은 Picked라 하자.

 

가장 긴 오름차순 수열을 구하기 위해 cnt라는 0으로 초기화된 배열이 필요하다.

만약 Picked와 Standard 사이에 "Picked보다 크면서 Standard보다 작은 값"이 존재한다면,

해당 값의 cnt에 1을 더한 값을Picked의 cnt에 삽입한다.

만약 Picked가 Standard보다 크다면 오름차순 수열을 이룰 수 없으므로 cnt를 0으로 유지한다.

 

해당 부분을 코드로 구현하기 위해 temp 변수를 선언하고 

Picked에서 Standard까지의 수열 값을 검사하며 "Picked 보다 큰 값"에 대해

temp = max(temp, "Picked보다 큰 값의 cnt" +1)와 같은 코드를 작성하였다.

이로써 Picked의 cnt는  Picked ~ Standard을 이루는 수열에서

Picked가 부분 수열의 시작이고 Standard가 부분 수열의 끝일 때 가장 긴 오름 차순 수열의 길이를 의미한다.

 

좌측 Picked의 cnt값은 Max_left와 비교하여 가장 큰 cnt의 값이 Max_left에 최종적으로 저장된다.

 

\(S_{k}\)의 우측에 대해서도 동일한 과정으로 진행된다.

다른 점이라면 Picked가 수열의 좌측으로 이동하며 변하는 것이 아닌,

Picked가 수열의 우측으로 이동하며 값이 변경된다는 점이다.

 

우측 Picked의 cnt값 또한 Max_right와 비교하여 가장 큰 cnt의 값이 Max_right에 최종 저장될 것이다.

 

\(S_{k}\)는 0 ~ N-1 인덱스에 해당하는 값을 가지며 변경되기 때문에

최종 출력 결과인 Max = max(Max, Max_left + Max_right) + 1이 된다.

(+1을 하는 이유는 Max_left와 Max_right에는 Standard의 개수가 포함되지 않기 때문이며

Max는 최종 출력 결과, max는 두 값의 최댓값을 반환하는 함수를 의미한다.)

 

코드

#include <iostream>
#include <algorithm>
#include <string.h>

using namespace std;

int N;
int Max;
int arr[1001];
int cnt[1001];

void init();
void input();
void Solve();

void init()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
}

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

void Solve()
{
    for (int i = 0; i < N; i++)
    {
        int Standard = arr[i];
        memset(cnt, 0, sizeof(cnt));

        int Max_left = 0;
        int Max_right = 0;

        // left (0 ~ i-1)
        for (int j = i - 1; j >= 0; j--)
        {
            int Picked = arr[j];

            if (Picked >= Standard)
                continue;

            int temp = 0;

            // j+1 ~ i
            for (int t = j + 1; t <= i; t++)
            {
                if (Picked < arr[t])
                {
                    temp = max(temp, cnt[t] + 1);
                }
            }
            cnt[j] = temp;
            Max_left = max(Max_left, temp);
        }

        // right (i+1 ~ N-1)
        for (int j = i + 1; j < N; j++)
        {
            int Picked = arr[j];

            if (Picked >= Standard)
                continue;

            int temp = 0;

            // j-1 ~ i
            for (int t = j - 1; t >= i; t--)
            {
                if (Picked < arr[t])
                {
                    temp = max(temp, cnt[t] + 1);
                }
            }
            cnt[j] = temp;
            Max_right = max(Max_right, temp);
        }

        Max = max(Max, Max_left + Max_right);
    }
    cout << Max + 1;
}

int main()
{
    init();
    input();
    Solve();

    return 0;
}