[백준/코틀린] 9465번: 스티커

링크

9465번: 스티커

풀이

dp[i][j]: i번째 줄의 j번째 스티커까지 고려했을 때의 최대 누적 합

인접한 스티커는 동시에 선택할 수 없으므로,
현재 스티커를 선택하는 경우와 선택하지 않는 경우로 나눠서 생각합니다.

즉, (i, j)까지의 최대 누적 합은 다음 두 가지 중 하나로 결정됩니다.

• 현재 스티커 선택 + 왼쪽 대각선 스티커까지의 최대 누적 합
• 현재 스티커 미선택 + 왼쪽 스티커까지의 최대 누적 합

가장 왼쪽 스티커부터 오른쪽 스티커까지 순차적으로 배열을 채워 나가며,
마지막 스티커까지 고려했을 때의 최대 누적 합을 구합니다.

코드

fun main() = repeat(readln().toInt()) {
    val n = readln().toInt()
    val sticker = List(2) { readln().split(" ").map { it.toInt() } }
    val dp = Array(2) { IntArray(n + 1) }

    repeat(n) {
        dp[0][it + 1] = maxOf(sticker[0][it] + dp[1][it], dp[0][it])
        dp[1][it + 1] = maxOf(sticker[1][it] + dp[0][it], dp[1][it])
    }

    println(maxOf(dp[0][n], dp[1][n]))
}