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

백준

---

🤔문제 이해

어느 한 숫자를 기준으로 왼쪽에는 감소하는 숫자들이, 오른쪽에는 증가하는 숫자들이 오는 부분 수열을 찾는 문제이다.

이때, 같은 숫자가 연속적으로 나올 수 없다.

---

💡첫번째 아이디어

가장 긴 증가하는 부분 수열의 응용 버전이었다. 

 

🔥풀이🔥

dp_in[i]는 i번째 수를 마지막 수로 했을 때 증가하는 수의 개수를 의미하고,

dp_de[i]는 i번째 수를 첫번째 수로 했을 때 감소하는 수의 개수를 의미한다.

 

1. dp_in과 dp_de는 모두 1로 초기화한다.

2. 앞에서부터 차례대로 현재 숫자가 다음 숫자보다 크다면, 현재 dp_in과 이전값 dp_in에 1을 더한 값 중에서 더 큰 값을 dp_in의 현재값에 넣어준다.

3. 뒤에서부터 차례대로 현재 숫자가 다음 숫자보다 크다면, 현재 dp_de와 이전값 dp_de에 1을 더한 값 중에서 더 큰 값을 dp_de의 현재값에 넣어준다.

4. dp_in과 dp_de의 i번째 수는 겹치므로 dp_in과 dp_de를 더하고 1을 빼준 값들을 비교해서 가장 큰 값을 출력한다.

 

❌트러블 슈팅

위 풀이에서의 4번에서 dp_in + dp_de를 해줄 때 겹치는 값 1을 빼주지 않아서 틀렸었다.

---

#include <iostream>
#include <cmath>

using namespace std;

int dp_in[1001];
int dp_de[1001];
int arr[1001];
int n;

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

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

    for (int i = 0; i < n; i++) {
        dp_in[i] = 1;
        dp_de[i] = 1;
    }

    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (arr[j] < arr[i]) {
                dp_in[i] = max(dp_in[i], dp_in[j] + 1);
            }
        }
    }

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

    int result = dp_in[0] + dp_de[0] - 1;
    for (int i = 1; i < n; i++) {
        int tmp = dp_in[i] + dp_de[i] - 1;
        if (result < tmp) result = tmp;
    }
    cout << result;
}