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

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

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

풀이

1. 11053 번 문제를 응용하여 이중으로 처리하는 것으로 푼다.

2. 왼쪽에서 오른쪽으로 증가하는 부분 수열의 개수를 구한다. (1 .. N)

3. 오른쪽에서 왼쪽으로 증가하는 부분 수열의 개수를 구한다. (N downTo 1)

4. 2번 3번 dp 값을 더한 것 중 최대값을 구한다.

5. 중복이 있으므로 4번의 최대값에서 1을 뺀다.

 

- 증가하는 부분 수열을 구하는 법

A[6] = {10, 20, 10, 30, 20, 50} 이라는 수열이 있을 때,

dp[1] = A[1] > A[0]이기 때문에 dp[0] + 1

dp[2] = A[2] > A[1]이기 때문에 dp[1] + 1

dp[3] = A[3] < A[2] 이고 A[3] = A[1] 이기 때문에 dp[0]+1

dp[4] = A[4] > A[1], A[2], A[3] 이기 때문에 저장된 dp 중 제일 큰 값 + 1

 

이렇게 저장된 dp 값 중 가장 큰 값을 출력한다.

코드

import java.util.*

fun main(args: Array<String>) {
    val sc = Scanner(System.`in`)
    val N = sc.nextInt()
    val A = IntArray(N + 1)
    val dpL = IntArray(N + 1) // 왼쪽에서 오른쪽으로 증가하는 부분 수열
    val dpR = IntArray(N + 1) // 오른쪽에서 왼쪽으로 증가하는 부분 수열

    for (i in 1..N) {
        A[i] = sc.nextInt()
    }

    // 왼쪽에서 오른쪽으로 증가하는 부분 수열 DP
    for (i in 1..N) {
        var count = 0
        for (j in 1 until i) {
            if (A[i] > A[j]) {
                count = max(count, dpL[j])
            }
        }

        dpL[i] = count + 1
    }

    // 오른쪽에서 왼쪽으로 증가하는 부분 수열 DP
    for (i in N downTo 1) {
        var count = 0
        for (j in N downTo i) {
            if (A[i] > A[j]) {
                count = max(count, dpR[j])
            }
        }

        dpR[i] = count + 1
    }

    var max = Int.MIN_VALUE

    for (i in 1..N) {
        val value = dpL[i] + dpR[i] - 1
        if (max < value) {
            max = value
        }
    }

    println(max)
}

private fun max(a: Int, b: Int): Int {
    return if (a < b) b else a
}