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

바이토닉 부분 수열이란, 수열 S가 어떤 수 Sk를 기준으로 S1 < S2 < ... Sk-1 < Sk > Sk+1 > ... SN-1 > SN을 만족 하는 수열이다.

 

예를 들면 {10, 20, 30, 10} 은 30을 기준으로 위 식을 만족하기에 바이토닉 부분수열 이라고 할 수 있지만,
{10, 20, 30, 10, 20}은 20으로 인해 바이토닉 부분 수열이 아니다.

 

자 이제 가장 긴 바이토닉 부분 수열을 찾기 위한 작업을 알아보자.

 

가장 긴 바이토닉 부분 수열을 찾기 위해서는
첫번째, 자기 자신까지 증가하는 가장 긴 증가수열의 길이.
두번째,자기 자신부터 감소하는 가장 긴 감소수열의 길이.
를 알아야 할 것이다. 이를 모두 구한 후, 자기 자신이 중복 되므로, 두 수열의 길이의 합에서 1을 빼주면 될 것이다.

 

{1, 5, 2, 1, 4} 이라는 수열을 예로 들어 가장 각 원소마다의 가장 긴 증가/감소 수열의 길이를 구해보자.

 

가장 긴 증가 수열의 길이를 찾기 위해서는 두가지 작업이 필요하다.
1. 왼쪽의 원소들 중 현재 원소보다 작은 원소를 찾는다.
2. 찾은 원소 부터 현재의 원소 까지의 증가 수열의 길이를 찾는다. 증가 수열이 될 수 있다면 수열의 길이를 +1 해준다.
dp_up 배열에는 각 인덱스 까지의 최장 증가 수열의 길이를 추가해 준다.

 

arr[1]
1번 인덱스는 왼편에 있는 원소가 없으므로 가장 긴 증가 수열의 길이는 자기자신. 즉 1 일 것이다.
dp_up[1]=1

 

arr[2]
2번 인덱스는 왼편의 원소중 작은 원소가 1(arr[1])이다. 그러므로 1번 인덱스의 길이와 자기 자신의 길이(+1) 이 추가될 수 있다. dp_up[2] = dp_up[1] + 1
dp_up[2] = 2
dp_up : [1,2,0,0,0]

 

arr[3]
3번 인덱스는 왼편의 원소중 작은 원소는 1번 인덱스의 원소 뿐이다. 위와 같은 이유로 
dp_up[3] = 2
dp_up : [1,2,2,0,0]

 

arr[4]
4번 인덱스는 왼편의 원소중 자기 자신보다 작은 원소가 없으므로
dp_up[4] = 1
dp_up : [1,2,2,1,0]

 

arr[5]
5번 인덱스는 왼편의 원소중 자기 자신보다 작은 원소가 1,3,4번 인덱스에 존재한다. {1,2,1}
1번 인덱스를 선택 할 경우 dp_up[5] = dp_up[1] + 1 = 2
3번 인덱스를 선택 할 경우 dp_up[5] = dp_up[3] + 1 = 3
4번 인덱스를 선택 할 경우 dp_up[5] = dp_up[4] + 1 = 2
!!!!! 이거... 어떤걸 선택 해야 할지에 대한 문제가 생겼다. MAX 함수를 사용하기에는 뒤로 갈 수록 비교원소가 많아져 사용하기에는 시간도 오래 걸릴것 같으니 다른 방법을 생각해보자.
이미 3번 인덱스를 선택했을 경우에 최대 값이 나왔으므로, 다음 4번 인덱스의 값이 조건에 들어가지 않게 if문을 꾸려 주도록 하면 될 것이다!
dp_up[5] = 3
dp_up : [1,2,2,1,3]

 

--> 즉 위의 수열에서 최장 증가 수열의 길이는 3이 되는 것이다.

이렇게 최장 증가 수열을 찾을 수 있게 되었다! 사실 최장 감소 수열을 찾는 방식은 뒤에서 부터 같은 방식으로 검색 할 수 있으므로 for문의 순서만 바꾸어 주면 된다.

이 후 각 원소 각각의 최장 증가/감소 수열의 길이의 합에서 -1을 해주면 가장 긴 바이토닉 부분수열의 길이를 찾을 수 있게된다. (-1은 자기자신이 중복 되었으므로 빼주는것! 잊지 말자!)

<소스코드>

#include<iostream>
#define MAXQ 1001
using namespace std;
 
int n;
int arr[MAXQ];
int dp_up[MAXQ];
int dp_down[MAXQ];
 
void Input() {
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> arr[i];
}
 
void Solve() {
    int res = 0;
    for (int i = 1; i <= n; i++) {//증가 찾기
        dp_up[i] = 1;
        for (int j = 1; j <= i; j++) { //자기보다 작은것 찾기
            if (arr[j] < arr[i] && dp_up[i]<dp_up[j]+1) 
                dp_up[i] = 1 + dp_up[j];
        }
    }
    for (int i = n; i >=1; i--) {//감소 찾기
        dp_down[i] = 1;
        for (int j = n; j >=i; j--) { //자기보다 작은것 찾기
            if (arr[j] < arr[i] && dp_down[i]<dp_down[j] + 1)
                dp_down[i] = 1 + dp_down[j];
        }
    }
    for (int i = 1; i <= n; i++) {
        if (dp_up[i] + dp_down[i] - 1 > res)
            res = dp_up[i] + dp_down[i] - 1;
    }
    cout << res;
}
 
int main() {
    Input();
    Solve();
}

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

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