[백준/코틀린] 11053번: 가장 긴 증가하는 부분 수열

링크

11053번: 가장 긴 증가하는 부분 수열

풀이

dp[i]: i번째 원소를 마지막으로 하는 가장 긴 증가하는 부분 수열(LIS)의 길이

j < i인 인덱스에 대해 a[j] < a[i]인 경우,
j에서 끝나는 LIS 뒤에 a[i]를 이어 붙일 수 있으므로 dp[i]를 갱신합니다.

문제의 조건이 N ≤ 1,000이므로, 이중 반복문을 사용해 O(n²)로 해결할 수 있습니다.

코드

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

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

    println(dp.maxOrNull())
}