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

문제 링크 : www.acmicpc.net/problem/11054

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

이 문제는 백준 11053번 가장 긴 증가하는 부분 수열의 확장판이다.

 

문제 풀이는 다음과 같다.

1. 증가하는 수열과 감소하는 수열을 나눠서 바라본다. 때문에 배열은 총 3개가 필요한데, 아래의 배열들이 필요하다.

(1) 입력값 (2) 증가길이 (3) 감소길이

2. 정답변수의 초기값은 1로 선언해준다. 무슨일이 있어도 최소 증가길이는 1이 나올 수 밖에 없기 때문이다.

3. 증가하는 수열의 길이를 저장한다.

4. 감소하는 수열의 길이를 저장한다. 감소하는 수열은 증가하는 수열과 다르게 배열의 첫 번째가 아닌 끝에서 부터 시작된다. 첫 번째부터 시작하면 수가 옳바르게 저장될 수 없다.

5. 마지막으로 첫 번째부터 n번째까지 for문을 돌려서 정답값 > 증가수열[i] + 감소수열[i] - 1을 만족할 경우, 그 수를 정답값으로 저장한다.

이때 -1이 들어가는 이유는, 증가수열과 갑소수열 모두 i라는 숫자를 중복해서 저장하기 때문이다.

 

#include <iostream>
#define MAX 1001
using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int n = 0, ans = 1, arr[MAX], pl[MAX], mi[MAX];
    cin >> n;
    for(int i=1; i<=n; i++) {
        cin >> arr[i];
        pl[i] = 1;
        mi[i] = 1;
    }
    for(int i=2; i<=n; i++){ // 증가
        for(int j=1; j<i; j++){
            if(arr[i]>arr[j]&&pl[i]<pl[j]+1) pl[i] = pl[j]+1;
        }
    }
    for(int i=n; i>0; i--){
        for(int j=i+1; j<=n; j++){
            if(arr[i]>arr[j]&&mi[i]<mi[j]+1) mi[i] = mi[j]+1;
        }
    }
    for(int i=1; i<=n; i++){
        if(ans<pl[i]+mi[i]-1) ans = pl[i] + mi[i]-1;
    }
    cout << ans << "\n";
    return 0;
}