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

문제

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

풀이

• 메모이제이션
• i번째 가장 긴 증가하는 부분 수열을 구하려면 처음부터 i-1번째의 값을 순회해서 i번째 값이 순회한 값보다 클 때에만 dp 값을 비교하면 된다.
• i번째 값이 순회한 값보다 클 때에만 dp값을 비교하기 때문에 가장 긴 증가하는 부분 수열을 출력하기 위해서는 전체 dp 중 가장 큰 값을 출력해야한다.

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 dp = Array(n) { 1 }
    for (i in 1 until n) {
        for (j in 0 until i) {
            if (sequence[i] > sequence[j]) {
                dp[i] = max(dp[i], dp[j] + 1)
            }
        }
    }
    bw.write("${dp.maxOf { it }}")
    bw.close()
    br.close()
}

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