[백준 11054] 가장 긴 바이토닉 부분 수열 (C#, C++) - soo:bak

문제 링크

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

설명

N개의 수로 이루어진 수열이 주어지는 상황에서 N (1 ≤ N ≤ 1,000)과 수열이 주어질 때, 가장 긴 바이토닉 부분 수열의 길이를 구하는 문제입니다.

바이토닉 수열은 어떤 지점을 기준으로 왼쪽은 증가하고 오른쪽은 감소하는 수열입니다.

증가만 하거나 감소만 하는 수열도 바이토닉 수열에 포함됩니다.

접근법

각 위치를 바이토닉 수열의 꼭짓점(가장 큰 값)으로 생각하면 왼쪽은 증가 부분 수열, 오른쪽은 감소 부분 수열이 됩니다.

모든 위치에서 이를 계산하여 최댓값을 구합니다.

inc[i]를 i번째 원소를 마지막으로 하는 증가 부분 수열의 최대 길이로 정의하고, dec[i]를 i번째 원소를 첫 번째로 하는 감소 부분 수열의 최대 길이로 정의합니다.

이 때, i번째 원소를 꼭짓점으로 하는 바이토닉 길이는 inc[i] + dec[i] - 1입니다 (i가 중복 계산되므로 1을 뺌).

예를 들어 수열 [1, 5, 2, 1, 4, 3, 4, 5, 2, 1]에서:

• inc = [1, 2, 2, 1, 3, 3, 4, 5, 2, 1] (각 위치까지의 LIS 길이)
• dec = [1, 4, 2, 1, 3, 2, 2, 3, 2, 1] (각 위치부터의 감소 수열 길이)
• 인덱스 7(값 5): inc[7] + dec[7] - 1 = 5 + 3 - 1 = 7 (최댓값)
• 바이토닉 수열: 1, 2, 3, 4, 5, 2, 1

inc는 왼쪽에서 오른쪽으로 LIS DP를 수행하고, dec는 오른쪽에서 왼쪽으로 LIS DP를 수행합니다. 시간 복잡도는 O(N²)입니다.

---

Code

C#

using System;

namespace Solution {
  class Program {
    static void Main(string[] args) {
      var n = int.Parse(Console.ReadLine()!);
      var a = Array.ConvertAll(Console.ReadLine()!.Split(), int.Parse);
      var inc = new int[n];
      var dec = new int[n];
      Array.Fill(inc, 1);
      Array.Fill(dec, 1);

      for (var i = 0; i < n; i++) {
        for (var j = 0; j < i; j++) {
          if (a[j] < a[i] && inc[i] < inc[j] + 1)
            inc[i] = inc[j] + 1;
        }
      }

      for (var i = n - 1; i >= 0; i--) {
        for (var j = n - 1; j > i; j--) {
          if (a[j] < a[i] && dec[i] < dec[j] + 1)
            dec[i] = dec[j] + 1;
        }
      }

      var ans = 0;
      for (var i = 0; i < n; i++)
        ans = Math.Max(ans, inc[i] + dec[i] - 1);

      Console.WriteLine(ans);
    }
  }
}

C++

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

typedef vector<int> vi;

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

  int n; cin >> n;
  vi a(n);
  for (int i = 0; i < n; i++)
    cin >> a[i];

  vi inc(n, 1), dec(n, 1);

  for (int i = 0; i < n; i++) {
    for (int j = 0; j < i; j++) {
      if (a[j] < a[i] && inc[i] < inc[j] + 1)
        inc[i] = inc[j] + 1;
    }
  }

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

  int ans = 0;
  for (int i = 0; i < n; i++)
    ans = max(ans, inc[i] + dec[i] - 1);

  cout << ans << "\n";

  return 0;
}