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

 

 LIS를 응용한 DP 문제. LIS 알고리즘을 공부했거나 관련 문제를 풀어봤다면 어렵지 않게 풀이 방법을 떠올릴 수 있다. 기준이 될 인덱스를 정해두고, 앞부분에 대한 LIS를 구하고 뒷부분에 대한 LDS를 구해서 더한 값에 1을(기준 값이 포함되어야 하기 때문에) 더해주면 끝이기 때문이다.

 

 다만 내 접근 방식대로 풀려면 수열의 처음부터 끝까지 모두 기준으로 잡고 한 번씩 구해봐야 하기 때문에, LIS와 LDS 구하는 알고리즘은 O(n log n)인 알고리즘을 사용해야 한다. 굳이 이 방법이 아니어도 O(n^2) 알고리즘을 두 번 사용하는 형태로 구해도 될 것 같긴하다.

 LIS를 기준으로 간략하게 적자면,

 - 길이별로 최적 LIS의 마지막 값을 저장해둘 배열(여기선 lis로 지칭)을 생성해 둔다. 

 - 수열의 처음부터 기준이 되는 인덱스 전까지 탐색하기 시작한다.

 - 탐색 중인 수가 lis의 끝 값보다 크다면, 앞에서 만든 가장 긴 lis의 끝 값보다 탐색 중인 값이 크다는 뜻이다. 즉, 탐색 중인 값을 붙여도 LIS가 깨지지 않는다는 의미이므로, lis의 끝에 탐색 중인 수를 추가해 준다. 

 - 탐색 중인 수가 lis의 끝 값보다 작다면, lis 배열에 탐색 중인 값이 들어갈 수 있는 lower bound를 찾는다. 탐색된 lis배열 내의 위치가 의미하는 것은 그 길이에(길이는 위치에 해당하는 인덱스 값이 된다) 해당하는 lis 끝 값보다, 탐색 중인 수가 작거나 같다는 의미이다. LIS를 최적으로 만들기 위해서는, 같은 길이라면 끝 값이 작을수록 무조건 유리하므로 찾아낸 lower bound 위치에 탐색된 값을 assign 해준다.

 - 최종적으로 완성된 lis 배열의 길이를 통해 실제 만들 수 있는 LIS의 길이를 알아낼 수 있다.

 

 이 때 주의해야 할 것은, lis 배열을 구성하는 값들은 기준이 되는 값보다는 작아야 한다는 것이다. 그래야 바이토닉 수열의 정의에 부합할 테니까. 따라서 탐색 과정에서 이 조건에 맞지 않는 값은 lis 배열을 채워나갈 때 이용하지 않아야 한다.

 

 그리고 기준 값 뒷 부분은 위의 로직을 LDS 형태로 변형해서 구하면 되니까 사실상 거의 유사한 로직이다. 나는 C++을 통해 구현하므로, stl의 lower_bound 함수에 Compare 인자를 greater<int>()로 줘서 간단하게 구현했다.

 이 과정을 모든 수열 내 수들을 기준으로 반복하면서, LIS+기준 값+LDS에 해당하는 가장 긴 바이토닉 수열 길이를 찾아 출력한다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    vector<int> numArr(n);
    for(int i=0; i<n; i++) {
        cin >> numArr[i];
    }

    int longestLength = 0;

    for(int i=0; i<n; i++) {
        vector<int> prev;
        vector<int> subs;
        prev.push_back(0);
        subs.push_back(numArr[i]);

        for(int j=0; j<i; j++) {
            if(numArr[j]>=numArr[i]) continue;
            if(numArr[j]>prev.back()) {
                prev.push_back(numArr[j]);
            } else {
                auto pos = lower_bound(prev.begin(), prev.end(), numArr[j]);
                if(pos!=prev.end()) {
                    *pos = numArr[j];
                }
            }
        }

        for(int j=i+1; j<n; j++) {
            if(numArr[j]<subs.back()) {
                subs.push_back(numArr[j]);
            } else {
                auto pos = lower_bound(subs.begin(), subs.end(), numArr[j], greater<int>());
                if(pos!=subs.end() && pos!=subs.begin()) {
                    *pos = numArr[j];
                }
            }
        }

        longestLength = max(longestLength, (int)prev.size() + (int)subs.size() - 1);
    }

    cout << longestLength;
}

 

 

+ 포스팅을 작성하면서 O(n^2) 알고리즘을 두 번 사용해서 풀어도 되지 않을까 싶어서 풀어봤는데, 문제 없이 동작했다. 이쪽은 각 인덱스 별 LIS와 LDS가 메모이제이션 하는 배열에 남기 때문에, 이 쪽이 시간 복잡도도 더 작을거라고 예상했는데 예상이 맞았다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    vector<int> numArr(n);
    for(int i=0; i<n; i++) {
        cin >> numArr[i];
    }

    vector<int> lis(n, 1);
    vector<int> lds(n, 1);

    for(int i=1; i<n; i++) {
        for(int j=i-1; j>=0; j--) {
            if(numArr[j]<numArr[i]) {
                lis[i] = max(lis[i], lis[j]+1);
            }
        }

        int ldsInd = n-1-i;
        for(int j=ldsInd+1; j<n; j++) {
            if(numArr[j]<numArr[ldsInd]) {
                lds[ldsInd] = max(lds[ldsInd], lds[j]+1);
            }
        }
    }

    int longestLength = 0;
    for(int i=0; i<n; i++) {
        longestLength = max(longestLength, lis[i]+lds[i]-1);
    }

    cout << longestLength;
}