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

문제

 

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

 

---

풀이

 

 DP를 활용하여 해결할 수 있으며 주어진 예제 입력을 dp 배열로 메모이제이션한다면 다음과 같다.

arr	10	20	10	30	20	50
dp	1	2	1	3	2	4

 10은 10보다 작은 값이 없기 때문에 길이가 1인 수열이 되고, 50은 10, 20, 30, 50으로 길이가 4인 수열이 된다. 이를 DP로 해결하기 위한 반복문을 만들어보자.

 

 입력 받은 배열을 순회하며 각 원소에 대해 이전 원소들과 비교한다. 만약 현재 원소가 이전 원소보다 큰 경우, DP 배열을 갱신한다. 이전 원소의 dp값 + 1 과 자기 자신의 DP값을 비교하여 더 큰 수를 저장한다. 이 과정을 반복하면 DP배열에는 각 원소를 끝으로하는 가장 긴 증가하는 부분 수열의 길이가 저장된다. 이 중 최댓값을 찾아 출력해주면 된다.

 

---

코드

 

import kotlin.math.*

fun main() {
    val br = System.`in`.bufferedReader()
    val bw = System.out.bufferedWriter()

    val num = br.readLine().toInt()
    val arr = br.readLine().split(' ').map { it.toInt() }
    val dp = IntArray(num){1}

    for(i in 0 until num) {
        for(j in 0 until i) {
            if(arr[i]>arr[j]) {
                dp[i] = max(dp[i], dp[j]+1)
            }
        }
    }

    bw.write("${dp.max()}")
    bw.flush()
    bw.close()
    br.close()
}