[오알] 백준 1912번 연속합

• 문제링크

dp문제다.
간단하게 풀 수 있는데 이해하는게 조금 어려웠다.

순서대로 더하고 만약 지금 그냥 있는 수가 더 크다면 그 수를 dp에 저장하면 되는데 이렇게 말하면 어려우니

list = { 2 1 -4 3 4 -4 6 5 -5 1 } 로 보면

dp[0] = 2 -> list[0]
dp[1] = 3 -> list[0] + list[1]
dp[2] = -1 -> list[0] + list[1] + list[2]
dp[3] = 3 -> list[0] + list[1] + list[2] < list[3]라서 list[3]

그럼 이제 여기서 부터는 list[3]부터 다시 연속합을 구하는 원리가 되는 것이다.

dp[4] = 7 -> list[3] + list[4]
dp[5] = 3 -> list[3] + list[4] + list[5]
dp[6] = 9 -> list[3] + list[4] + list[5] + list[6]
dp[7] = 14 -> list[3] + list[4] + list[5] + list[6] + list[7]
dp[8] = 9 -> list[3] + list[4] + list[5] + list[6] + list[7] + list[8]
dp[9] = 10 -> list[3] + list[4] + list[5] + list[6] + list[7] + list[8] + list[9]

이런식으로 들어가게 되어서
maxOf(dp[i - 1] + list[i], list[i]) 이 코드만으로 문제가 해결이 되는 것이다.
그리고 dp 중 가장 큰 숫자를 반환하면 해결~~

git

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.StringTokenizer

private fun setDp(list: IntArray): IntArray {
    val n = list.size

    val dp = IntArray(n)
    dp[0] = list[0]

    for (i in 1 until n) {
        dp[i] = maxOf(dp[i - 1] + list[i], list[i])
    }

    return dp
}

fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val n = br.readLine().toInt()
    val list = StringTokenizer(br.readLine()).run { IntArray(n) { nextToken().toInt() } }

    val dp = setDp(list)

    println(dp.maxOrNull())
}