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

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

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

풀이

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 dp = IntArray(N + 1)

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

    for (i in 1..N) {
        var count = 0
        for (j in 0 until i) {
            if (A[i] > A[j]) {
                count = max(count, dp[j])
            }
        }

        dp[i] = count + 1
    }

    var result = Int.MIN_VALUE
    for (i in 1..N) {
        if (result < dp[i]) {
            result = dp[i]
        }
    }

    println(result)
}

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