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

코드

import kotlin.math.max

fun main() {
    val N = readLine()!!.toInt()

    val arr = readLine()!!.split(" ").map { it.toInt() }.toIntArray()

    val left = findDp(N, arr)
    val right = findDp(N, arr.reversedArray()).reversedArray()

    var answer = 0
    for (i in 0..left.lastIndex) {
        answer = max(answer, left[i] + right[i] - 1)
    }
    println(answer)
}

private fun findDp(N: Int, arr: IntArray): IntArray {
    val dp = IntArray(N)
    dp[0] = 1
    for (i in 1 until N) {
        dp[i] = 1
        for (j in 0 until i) {
            if (arr[i] > arr[j])
                dp[i] = max(dp[i], dp[j] + 1)
        }
    }
    return dp
}

풀이

이 문제를 풀기 전에 가장 긴 부분 수열 구하기에 대해서 풀고 오는 것을 권장합니다. 백준 - 가장 긴 부분 수열 구하기

위 풀이는 코드는 짧지만 생각보다 어려운 문제입니다.(풀이에 있어 아이디어가 필요함)

1. 먼저 -> 순으로 증가하는 부분 수열을 구합니다.
2. 다음 <- 순으로 증가하는 부분 수열을 구합니다. (저는 reverse로 배열을 변환시켜 넣어주어 풀었습니다.)
3. 각 인덱스에 맞춰 left[i]+right[i]를 하고 나서 -1을 해주면서 가장 큰 값을 찾습니다.

->,<- 양방향으로 증가하는 부분 수열을 찾는 이유는 간단합니다.
S1 < S2 < ... Sk-1 < Sk > Sk+1 > ... SN-1 > SN
여기서
->의 부분은 S1 < S2 < ... Sk-1 < Sk을 구하는 것이고
<-의 경우는 Sk > Sk+1 > ... SN-1 > SN을 구한 것입니다.

이 후 이 두개의 값을 더하면 (자기 자신 포함 left 증가) + (자기 자신 포함 right 증가)를 구하게 되는데 이 때 자기 자신을 2번 포함을 했으므로 마지막에 1을 빼준 것입니다.

예: 1 5 2 1 4 3 4 5 2 1

증가하는 수열 찾기
->
left : 1 2 2 1 3 3 4 5 1 1

<-
right:1 5 2 1 4 3 3 3 2 1

1 2 2 1 3 3 4 5 1 1
1 5 2 1 4 3 3 3 2 1

참고

만약 더 최적화를 하고 싶으시다면 증가 수열을 찾는 과정을 이중 for문이 아닌 이분 탐색을 통해서 찾는 방법을 택하시면 됩니다.

출처

백준 - 가장 긴 바이토닉 부분 수열