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

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

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

C++

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> per;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n, input;
    cin >> n;
    vector<int> memo(n);        // 거기까지의 최대 길이
    vector<int> memo2(n);        // 거기서부터의 최대 길이

    for (int i = 0; i < n; i++) {
        cin >> input;
        per.push_back(input);   // 들어가 있는 실제 수
    }

    memo[0] = 1;
    for (int i = 1; i < n; i++) {
        int max = -1;
        bool isMax;
        isMax = false;
        for (int j = 0; j < i; j++) {
            if (per[j] < per[i] && memo[j] > max) {
                max = memo[j];
                isMax = true;
            }
        }
        if (isMax == true) memo[i] = max + 1;
        else memo[i] = 1;
    }

    reverse(per.begin(), per.end());
    memo2[0] = 1;
    for (int i = 1; i < n; i++) {
        int max = -1;
        bool isMax;
        isMax = false;
        for (int j = 0; j < i; j++) {
            if (per[j] < per[i] && memo2[j] > max) {
                max = memo2[j];
                isMax = true;
            }
        }
        if (isMax == true) memo2[i] = max + 1;
        else memo2[i] = 1;
    }
    reverse(memo2.begin(), memo2.end());

    int MAX = 1;
    for (int i = 0; i < n; i++)
        if (MAX < memo[i]+memo2[i]) MAX = memo[i]+memo2[i];

    cout << MAX-1 << endl;

    return 0;
}

 

11053 가장 긴 증가하는 부분 순열 문제의 아이디어를 조금만 변형하면 된다.

memo[i]가 i번째까지 중의 최대 증가 수열 길이를 저장했다면 memo2[i]는 i번째 부터 끝가지 중의 최대 증가 길이를 저장한다.

알고리즘을 두 번 짜기 귀찮은? 측면이 있어서 <algorithm>에 정의되어 있는 reverse를 이용해 vector 원소 순서를 거꾸로 바꾸어 계산했다.

 

최종 값들은 {(처음에서 i번째 원소까지 중의 최대 등가 수열 길이) + (i번째 원소에서 마지막 원소까지 중의 최대 증가 수열 길이)}이고, 이 값들 중 최대치 -1 이 결과 출력값이다.

 

1을 빼주는 이유는 자기 자신을 중복해서 세기 때문이다.