[백준] 1965번: 상자넣기 - Kotlin[코틀린]

문제

 

1965번: 상자넣기

---

풀이

 

 이 문제는 최장 증가 수열(LIS, Longest Increasing Subsequence)을 구하는 문제로, 동적 프로그래밍(DP)을 활용하여 해결할 수 있다.

 

 입력받은 배열에서 반복문을 통해 현재 위치에서 앞의 원소들의 값과 비교하며 값을 갱신하면 된다. 만약 앞의 원소가 현재 원소보다 작다면 상자에 넣을 수 있으므로 해당 위치의 값 + 1을 현재 위치의 DP값과 비교하여 갱신해주면 된다.

 

 [1, 6, 1, 7, 5, 8]에 대해 LIS을 구하는 알고리즘을 살펴보면 다음과 같다.

 

 - 1: 현재 위치에서 이전 원소가 없으므로 LIS 길이는 1로 초기화된다. DP: [1, 1, 1, 1, 1, 1]
 - 6: 이전 원소인 1보다 크기 때문에 6을 포함한 LIS 길이를 갱신한다. DP: [1, 2, 1, 1, 1, 1]
 - 1: 현재 위치보다 작은 이전 원소가 없으므로, LIS는 변하지 않는다. DP: [1, 2, 1, 1, 1, 1]
 - 7: 이전 원소인 1, 6 중 가장 긴 LIS 길이에 1을 더한 값으로 갱신한다. DP: [1, 2, 1, 3, 1, 1]
 - 5: 이전 원소인 1의 LIS 길이에 1을 더한 값으로 갱신한다. DP: [1, 2, 1, 3, 2, 1]
 - 8: 이전 원소인 1, 6, 5, 7 중 가장 긴 LIS 길이에 1을 더한 값으로 갱신한다. DP: [1, 2, 1, 3, 2, 4]

 

---

코드

 

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 } // 자기 자신의 길이 1

    for(i in 1 until num) {
        for(j in 0 until i) { // 앞의 원소와 비교
            if(arr[i] > arr[j]) {
                dp[i] = maxOf(dp[i], dp[j] + 1)
            }
        }
    }

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