[백준/코틀린] 11054번: 가장 긴 바이토닉 부분 수열

링크

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

풀이

바이토닉 부분 수열이란, 어떤 수열이 먼저 순증가한 뒤 순감소하는 형태를 말합니다.
순증가 또는 순감소 부분이 비어 있어도 바이토닉 수열로 간주합니다.

dp1[i]: 수열의 왼쪽에서부터 시작하는 가장 긴 증가하는 부분 수열(LIS)의 길이
dp2[i]: 수열의 오른쪽에서부터 시작하는 가장 긴 증가하는 부분 수열(LIS)의 길이

우선 왼쪽에서 오른쪽으로 탐색하며,
j < i인 인덱스에 대해 a[j] < a[i]이면 dp1[i]를 갱신합니다.

이후 오른쪽에서 왼쪽으로 탐색하며,
j > i인 인덱스에 대해 a[j] < a[i]이면 dp2[i]를 갱신합니다.
이는 역방향 LIS와 동일합니다.

i를 꼭짓점으로 하는 바이토닉 부분 수열의 길이는 dp1[i] + dp2[i] - 1입니다.
모든 i에 대해 dp1[i] + dp2[i] - 1의 최댓값이 정답입니다.

i번째 원소가 두 수열에 모두 포함되므로, 중복을 제거하기 위해 1을 빼줍니다.

코드

fun main() {
  val n = readln().toInt()
  val a = readln().split(" ").map { it.toInt() }
  val dp1 = MutableList(n) { 1 }
  val dp2 = MutableList(n) { 1 }

  for (i in 0 until n) {
    for (j in 0 until i) {
      if (a[j] < a[i]) {
        dp1[i] = maxOf(dp1[i], dp1[j] + 1)
      }
    }
  }

  for (i in n - 1 downTo 0) {
    for (j in i + 1 until n) {
      if (a[j] < a[i]) {
        dp2[i] = maxOf(dp2[i], dp2[j] + 1)
      }
    }
  }

  println((0 until n).maxOf { dp1[it] + dp2[it] } - 1)
}

연관 문제

• [백준/코틀린] 11053번: 가장 긴 증가하는 부분 수열 - LIS: O(n²)