[백준] 가장 긴 바이토닉 부분 수열 - 골드 3 (Kotlin)

문제

수열 S가 어떤 수 Sk를 기준으로 S1 < S2 < ... Sk-1 < Sk > Sk+1 > ... SN-1 > SN을 만족한다면, 그 수열을 바이토닉 수열이라고 한다.

예를 들어, {10, 20, 30, 25, 20}과 {10, 20, 30, 40}, {50, 40, 25, 10} 은 바이토닉 수열이지만, {1, 2, 3, 2, 1, 2, 3, 2, 1}과 {10, 20, 30, 40, 20, 30} 은 바이토닉 수열이 아니다.

수열 A가 주어졌을 때, 그 수열의 부분 수열 중 바이토닉 수열이면서 가장 긴 수열의 길이를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000)

출력

첫째 줄에 수열 A의 부분 수열 중에서 가장 긴 바이토닉 수열의 길이를 출력한다.

풀이

이 전에 풀었던 가장 긴 증가하는 부분 수열 문제가 떠오르긴 했지만 응용하지 못해서 검색을 해보았다.
이 문제는 좌 -> 우 방향으로 가장 긴 증가하는 부분 수열을 구하고,
우 -> 좌 방향으로 다시 가장 긴 증가하는 부분 수열을 구한다음에 두 수열의 각 값을 더한 뒤 -1 을 해주면 된다.
무슨 소리냐면 예제 입력 1 5 2 1 4 3 4 5 2 1 의 경우를 보면
가장 긴 증가하는 부분 수열을 구했을 때 1 5 2 1 4 3 4 ''5'' 2 1 의 값이 가장 큰 값 5 가 된다.
즉, 1 5 2 1 4 3 4 5 2 1 가 되고,
반대 방향으로 가장 긴 증가하는 부분 수열을 구했을 때
1 5 2 1 4 3 4 5 2 1
해당 길이 3 을 더한 뒤 -1 을 하면 7 의 최대 길이가 구해진다.
이는 우리가 구하고자 하는 가장 긴 바이토닉 수열의 길이가 된다.

사실 문제를 보고 이렇게 떠오르기는 쉽지 않았지만 하나의 경우라고 생각하고 접근방법을 그냥 외우기로 했다.

소스 코드

import kotlin.math.max

fun main(args: Array<String>) {
/*
10
1 5 2 1 4 3 4 5 2 1
*/
    val N = readLine()!!.toInt()
    val dpL = IntArray(N+1) {1}
    val dpR = IntArray(N+1) {1}

    val list = readLine()!!.split(' ').map { it.toInt() }

    for (i in 1 until N) {
        for (j in 0 until i) {
            if (list[i] > list[j]) {
                dpL[i] = max(dpL[j]+1, dpL[i])
            }
        }
    }

    for (i in N-2 downTo 0) {
        for (j in N-1 downTo i) {
            if (list[i] > list[j]) {
                dpR[i] = max(dpR[j]+1, dpR[i])
            }
        }
    }

    println(dpL.mapIndexed { index, i -> i + dpR[index] }.maxOf { it-1 })
}