백준 11055 가장 큰 증가 부분 수열 Kotlin (dp)

문제 출처 : https://www.acmicpc.net/problem/11055

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

문제

수열 A가 주어졌을 때, 그 수열의 증가 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가 부분 수열은 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 이고, 합은 113이다.

입력

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

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

출력

첫째 줄에 수열 A의 합이 가장 큰 증가 부분 수열의 합을 출력한다.

비슷한 문제

• 11053번. 가장 긴 증가하는 부분 수열
• 11054번. 가장 긴 바이토닉 부분 수열
• 11722번. 가장 긴 감소하는 부분 수열
• 12015번. 가장 긴 증가하는 부분 수열 2
• 12738번. 가장 긴 증가하는 부분 수열 3
• 14002번. 가장 긴 증가하는 부분 수열 4
• 14003번. 가장 긴 증가하는 부분 수열 5

알고리즘 분류

• 다이나믹 프로그래밍

풀이

2021.04.19 - [알고리즘 문제 풀이/백준] - 백준 11053 가장 긴 증가하는 부분 수열 c++,Kotlin (dp)

증가하는 부분 수열 시리즈

이 문제는 가장 큰! 증가하는 부분 수열이다.

dp[i] = i까지 증가하는 부분 수열 중 가장 큰 부분 수열

n이 1000이기 때문에 간단하게 2중 포문으로 풀 수 있다.

인덱스가 i일 때 0~j(i-1)인덱스 중에서 input[i]보다 작은 값이 있다면 dp[j] + input[i]를 dp[i]에 삽입한다.

이때 기존에 있던 dp[i]보다 새로 들어올 dp[j] + input[i]가 더 큰 경우만 삽입하여 dp[i]는 가장 큰 값만 가지고 있음을 보장한다.

코드

val br = System.`in`.bufferedReader()
fun getIntList() = br.readLine().split(' ').map { it.toInt() }
fun getInt() = br.readLine().toInt()

fun main() = with(System.out.bufferedWriter()) {
    val n = getInt()
    val input = getIntList()
    val dp = IntArray(n)
    var answer = 0
    for (i in 0 until n) {
        dp[i] = input[i]
        for(j in 0 until i){
            if(input[i] > input[j]){
                if(dp[i] < dp[j]+input[i]){
                    dp[i] = dp[j] + input[i]
                }
            }
        }
        answer = answer.coerceAtLeast(dp[i])
    }
    write("$answer")
    close()
}