[ 백준 11055 ] - 가장 큰 증가 부분 수열 (Kotlin)

 

11055번: 가장 큰 증가 부분 수열

 

문제 이해 & 기본 개념

• 수열에서 증가하는 부분 (이어질 필요 x)에서 가장 합이 큰 경우를 찾아야하는 문제

---

중요 포인트

• 모든 경우의 수를 보는 방법도 있긴 하겠지만, 중복된 연산이 많이 발생
• 중복된 연산을 줄이기 위해 dp를 사용하면 간단하게 풀 수 있음

---

최종 풀이

• 점화식

dp[i] = max(dp[i], dp[j] + a[i])

• i는 현재 위치, j는 이전에 선택된 원소의 위치
• dp[i]는 i까지의 최대 합

---

 

소스 코드

import kotlin.math.max

lateinit var dp:Array<Int>

fun solve(list:List<Int>):Int{
    for (i in list.indices){
        // i = 먼저 선택되는 부분
        dp[i] = max(dp[i], list[i])
        for (j in i+1 until list.size){
            if(list[i] >= list[j]) continue // 다음 수가 작으면 패스
            dp[j] = max(dp[j], dp[i] + list[j])
        }
    }

    return dp.maxOrNull()!!
}

fun main(){
    val n = readln().toInt()
    val list = readln().split(" ").map { it.toInt() }
    dp = Array(n){0}

    println(solve(list))
}