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

📌 문제 출처: BOJ 11054 - 가장 긴 바이토닉 부분 수열

---

제목

( 7/29 - class3 : 백준11054 )

---

문제 유형

• 다이나믹 프로그래밍 (DP)
• 가장 긴 증가하는 부분 수열 (LIS)
• 가장 긴 감소하는 부분 수열 (LDS)
• 바이토닉 수열 (Bitonic Sequence)

---

풀이 방법 도출

• 각 인덱스를 기준으로 좌우로 증가/감소하는 LIS를 모두 구함
• dpL[i]: 왼쪽에서 i까지 증가하는 LIS 길이
• dpR[i]: 오른쪽에서 i부터 감소하는 LIS 길이
• 최종 결과는 dpL[i] + dpR[i] - 1의 최대값
  • 중복된 i를 두 번 세지 않기 위해 -1

---

시간 복잡도

• LIS + LDS 각각 O(N²)
• 전체 시간 복잡도: O(N²) (N ≤ 1000이므로 충분히 가능)

---

코드

#include <bits/stdc++.h>
using namespace std;

#define X first
#define Y second

using ll = long long;

int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);

  int n;
  cin >> n;
  vector<int> a(n), dpL(n, 1), dpR(n, 1);
  for(int i=0;i<n;i++) cin >> a[i];

  // dpL LIS forward
  for(int i=0;i<n;i++) {
    for(int j=0;j<i;j++) {
      if(a[j] < a[i]) dpL[i] = max(dpL[i], dpL[j]+1);
    }
  }

  // dpR LDS backwards

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

  int res = 0;
  for(int i=0;i<n;i++)
    res = max(res, dpL[i] + dpR[i] - 1);

  cout << res;
}