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

문제

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

n개의 수열을 입력받아 가장 긴 바이토닉 수열의 길이를 출력하면 되는 문제입니다.

바이토닉 수열이란 오름차순으로 증가하다가 내림차순으로 감소하는 수열을 말합니다.

예를 들어 {1, 2, 5, 4, 3} 은 바이토닉 수열입니다.

 

해당 문제를 보면 이 문제와 매우 유사하다는 것을 알 수 있습니다.

다만 증가하는 것만이 아닌 감소하는 부분까지 생각해줘야 합니다.

위와 같은 배열이 있다고 가정해 봅시다.

여기서 dp 를 활용해 이전 문제에서 풀었던 방식을 사용해 가장 긴 증가하는 수열의 길이를 체크해 봅니다.

다음과 같이 LIS가 만들어 집니다.

 

그 다음으로 배열의 마지막 index부터 시작하여 가장 긴 감소하는 수열의 길이를 체크해 봅니다.

여기서 중요한 부분은 각 index 마다 LIS와 LDS를 합치게 되면 바이토닉 수열의 길이를 알 수 있습니다.

현재 바이토닉 배열에는 원소가 1개 중복되어 있는 상태 이기 때문에 여기서 -1을 해주면

가장 긴 바이토닉 수열은 5가 됩니다.

 

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

먼저 LIS 를 구하는 코드입니다.

평소처럼 왼쪽에서 오른쪽으로 이동하면서 진행됩니다.

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

LDS를 구하는 코드입니다.

반대로 오른쪽에서 왼쪽으로 이동하면서 반복문이 진행됩니다.

오른쪽에서 왼쪽으로 이동하면서 오름차순을 체크해주면 결국 왼쪽에서 오른쪽으로 볼 때는 내림차순으로

되기 때문에 해당 방식으로 반복문을 진행하였습니다.

int ans = 0;
for (int i = 0; i < n; i++) {
	ans = max(up[i] + down[i] - 1, ans);
}
cout << ans;

마지막으로 LIS와 LDS를 더한 값에 -1 해준 값이 가장 큰 수를 찾아 내어 ans 변수값에 저장해 줍니다.

---

전체 코드입니다.

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <cmath>
#include <map>
#include <set>
#include <tuple>
#define MAX 2100000000
#define inf LONG_MAX
#define big(a, b) a > b ? a : b
using namespace std;
using ll = long long;
using ull = unsigned long long;
int arr[1001];
int up[1001];
int down[1001];
int main() {
    ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
    int n;
    cin >> n;
 
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    
    for (int i = 0; i < n; i++) {
        up[i] = 1;
        for (int j = 0; j < i; j++) {
            if (arr[j] < arr[i] && up[i]<up[j]+1)
                up[i] = up[j] + 1;
        }
    }
    for (int i = n - 1; i >= 0; i--) {
        down[i] = 1;
        for (int j = n - 1; j > i; j--) {
            if (arr[j] < arr[i] && down[i]<down[j]+1)
                down[i] = down[j] + 1;
        }
    }
    int ans = 0;
    for (int i = 0; i < n; i++) {
        ans = max(up[i] + down[i] - 1, ans);
    }
    cout << ans;
    
 
    
 
    return 0;
}