[백준] 1912번 연속합 in Kotlin

📜 문제

문제 링크

💡 나의 풀이

다이나믹 프로그래밍으로 문제를 풀었다.
입력으로 받은 숫자들을 배열 input에 담고, 2차원 dp table을 만들었다.

1. dp table 설정

dp[i][0] : input[i]을 포함하지 않았을 때, input의 인덱스 0부터 i까지만 봤을 때 연속합의 최댓값
dp[i][1] : input[i]를 포함할 때, input의 인덱스 0부터 i까지만 봤을 때 연속합의 최댓값

• dp[i][0]의 경우 dp[i]를 포함하지 않기 때문에 input의 인덱스 0부터 (i - 1)까지 고려해봤을 때 연속합이 최댓값이 되는 값을 선택하면 된다.
  (dp[i][0] = max(dp[i - 1][1], dp[i - 1][0]))
• dp[i][1]의 경우 dp[i]를 포함해야 하는데, input[i]가 이미 진행중인 연속합에 더해질 건지 새로운 연속합을 만들어낼 건지 선택해야 한다.
  (dp[i][1] = max(dp[i - 1][1] + input[i], input[i]))

2. 문제의 조건 중 "단, 수는 한 개 이상 선택해야 한다."를 만족시키기
만약 입력받은 숫자들이 모두 음수인 경우에는 1.의 풀이방법에서는 수를 하나도 선택하지 않는 것이 연속합의 최대라고 인식하기 때문에 따로 처리해주어야 한다. 이를 위해 dp[n - 1][0] == 0일 때 input에서의 최댓값이 정답이 되도록 코드를 작성했다.

⌨️ 코드

fun main() = with (System.`in`.bufferedReader()) {
        val n = readLine().toInt()
        val input = readLine().split(" ").map { it.toInt() }
        val dp = Array(n) { IntArray(2) }

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

        if (dp[n - 1][0] == 0) { // 한 개도 선택되지 않은 경우
            println(input.maxOrNull())
        } else {
            println(maxOf(dp[n - 1][0], dp[n - 1][1]))
        }
}

😄 느낀 점

dp문제 연습한 지 사흘만에 드디어 스스로 dp문제를 풀었다.
다른 사람들의 풀이를 보니까 더 간단한 방법이 있지만,, 그래도 나만의 dp table을 만들어서 문제를 풀어냈다는 사실이 너무나도 뿌듯했다,,!❤️