14002번: 가장 긴 증가하는 부분 수열 4 - Kotlin

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

문제

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.

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

출력

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

둘째 줄에는 가장 긴 증가하는 부분 수열을 출력한다. 그러한 수열이 여러가지인 경우 아무거나 출력한다.

 

 

나의 풀이

 이 문제는 DP를 사용해서 해결할 수 있는 문제이다. N의 개수가 1000개로 비교적 작은 범위가 주어지기 때문에, 시간복잡도가 O(N^2)가 되도 괜찮다고 생각하고 문제를 해결하려고 하였다.

 

 이 문제는 첫 번째부터 N번째까지 DP를 넣어주고 탐색하는 순서에서 0번째까지 또 탐색을 해야하기 때문에 O(N^2)의 시간복잡도를 가지게 된다. N의 개수의 범위가 작기에 이대로 진행하였다.

 

 나는 DP 배열을 2차원 배열로 List가 들어가게 설계하였다. 현재의 숫자가 이전 DP의 마지막 숫자보다 클 때에 현재 DP의 리스트를 이전 DP의 리스트로 복사하고, 현재 DP에 현재 숫자를 ADD 해주는 식으로 설계를 하였다.

 

 그리고 마지막에 DP 배열에서 리스트의 길이가 가장 긴 리스트를 찾고 해당하는 리스트의 길이와 리스트를 출력해주는 것으로 문제를 해결하였다.

 

import kotlin.math.max

fun main() = with(System.`in`.bufferedReader()) {
    val n = readLine().toInt()

    val num = readLine().split(" ").map { it.toInt() }.toIntArray()
    val dp = Array(n) { mutableListOf<Int>() }

    dp[0].add(num[0])

    for (i in 1 until n) {
        for (j in i - 1 downTo 0) {
            if (num[i] > dp[j].last()) {
                if (dp[i].size < dp[j].size) {
                    dp[i] = ArrayList(dp[j])
                }
            }
        }
        dp[i].add(num[i])
    }

    var maxIndex = 0
    for (i in 1 until n) {
        if (dp[i].size > dp[maxIndex].size) {
            maxIndex = i
        }
    }

    println(dp[maxIndex].size)
    dp[maxIndex].forEach {
        print("$it ")
    }
}