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

문제

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

풀이

• 메모이제이션
• 0 -> (n-1) 까지의 가장 긴 증가하는 부분 수열 계산
• (n-1) -> 0 까지의 가장 긴 증가하는 부분 수열 계산
• 위 두 개의 dp 값을 더한 값에 -1
• 두 개의 dp 값을 더한다는 의미는 dp 의 index 를 기준으로 오른쪽은 증가하는, 왼쪽은 감소하는 수열이 되기 때문에 그 중에 max 값을 계산하고, 동일한 index 를 증가하는 수열로 포함하고 있으니 -1 을 해주어야 한다.

import kotlin.math.max

fun main() {
    val br = System.`in`.bufferedReader()
    val bw = System.out.bufferedWriter()
    val n = br.readLine().toInt()
    val sequence = br.readLine().toString().split(" ").map { it.toInt() }
    val dp1 = Array(n) { 1 }
    val dp2 = Array(n) { 1 }
    for (i in 1 until n) {
        for (j in 0 until i) {
            if (sequence[i] > sequence[j]) {
                dp1[i] = max(dp1[i], dp1[j] + 1)
            }
        }
    }
    for (i in (n - 2) downTo 0) {
        for (j in (n - 1) downTo (i + 1)) {
            if (sequence[i] > sequence[j]) {
                dp2[i] = max(dp2[i], dp2[j] + 1)
            }
        }
    }
    bw.write("${dp1.mapIndexed { index, i -> i + dp2[index] }.maxOf { it - 1 }}")
    bw.close()
    br.close()
}

더 좋은 풀이 방법 있으면 댓글 달아주세요!!!