[ 백준 11054 ] 가장 긴 바이토닉 부분 수열 (C++) - DP, 브루트포스

---

🔗 문제 링크

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

문제 링크가 제대로 달리지 않아 링크 남겨두었습니다.

---

💡 문제 풀이 및 해석

1. 어떤 특정한 수를 기준으로 양쪽에서 증가하는 수열을 찾아야 한다.
2. N의 범위가 1000 이므로 한번에 검사하는 것이아닌 왼쪽과 오른쪽으로 증가하는 수열을 따로 찾아도 된다.
3. 한쪽으로 증가하는 부분 수열을 찾는 방법은 아래와 같다.
   1. 현재 index가 K라면, 0~K-1 까지의 수들을 모두 탐색한다.
   2. 이 때, K보다 작은 수들을 찾는다.
   3. 그 중에서 DP[찾은 수] + 1 > DP[K]라면 증가하는 부분 수열이므로 업데이트 해준다.
   4. 찾은 모든 수들에 대해서 3번을 반복하면 DP[K]가 최댓값을 갖는다.
4. 위 방식으로 좌우를 했을 때, rightDp와 leftDp를 더한다. 그 중 최대값 - 1이 문제의 정답임을 알 수 있다.
5. -1을 하는 이유는 arr[K] 위치가 2번 더해지기 때문이다.

---

⭐️ 정답 코드 및 설명

#include <iostream>
#include <vector>

using namespace std;

int N;
vector<int> arr;

int leftDp[1000];
int rightDp[1000];

void input(){
    cin>>N;
    for(int i=0; i<N; i++){
        int num; cin>>num;
        arr.push_back(num);
        leftDp[i]=1;
        rightDp[i]=1;
    }
}

void sol(){
    int answer=0;

    for(int i=1; i<N; i++){ // 현재 숫자
        for(int j=i-1; j>=0; j--){ // 비교군
            int postNum=arr[j];
            int curNum=arr[i];
            if(curNum > postNum){
                if(rightDp[i] < rightDp[j] + 1) {
                    rightDp[i] = rightDp[j] + 1;
                }
            }
        }
    }

    for(int i=N-2; i >= 0; i--){ // 현재 숫자
        for(int j=i+1; j < N; j++){ // 비교군
            int postNum=arr[j];
            int curNum=arr[i];
            if(curNum > postNum){
                if(leftDp[i] < leftDp[j] + 1) {
                    leftDp[i] = leftDp[j] + 1;
                }
            }
        }
    }

    for(int i=0; i<N; i++){
        answer=max(answer,rightDp[i]+leftDp[i]);
    }
    cout<<answer - 1;
}

int main() {

    input();
    sol();


    return 0;
}

---

🤔 문제 후기

DP라기 보다는 브루트포스에 가깝지 않나 싶기도 하다. 이런 종류의 문제를 몇번 풀어봤는데, 그 경험으로 문제를 보고 바로 어떤 방식으로 풀어야 하는지 생각났다. 물론 숫자가 커진다면 이런 방식으로 풀 수는 없을 것이다. N <= 10000 까진 괜찮겠지만, 100000 이상으로 넘어가는 순간 기하급수적으로 시간복잡도가 증가한다. 더 최적화 시킬 수 있는 방법은 없을까 생각해볼만한 문제였다.